| input | output |
|---|---|
BID 0.01 BID 10000 BID 5000 BID 5000 SALE 7000 3 DEL 5000 SALE 3000 3 SALE 0.01 3 QUIT |
0.06
|
分析：离散化+树状数组；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <hash_map> #include <queue> #include <stack> #include <vector> #include <list> #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define Lson L, mid, rt<<1 #define Rson mid+1, R, rt<<1|1 const int maxn=1e5+10; const int dis[][2]={0,1,-1,0,0,-1,1,0}; using namespace std; using namespace __gnu_cxx; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;} int n,m,k,t,a[maxn],num; double c[maxn]; ll ans; struct node { char a[10]; double b; int c; }op[maxn]; void add(int x,int y) { for(int i=x;i<=num;i+=(i&(-i))) { a[i]+=y; } } int get(int x) { int ans=0; for(int i=x;i;i-=(i&(-i))) ans+=a[i]; return ans; } int main() { int i,j; while(~scanf("%s",op[++n].a)&&op[n].a[0]!=‘Q‘) { scanf("%lf",&op[n].b); c[n]=op[n].b; if(op[n].a[0]==‘S‘)scanf("%d",&op[n].c); } n--; sort(c+1,c+n+1); num=unique(c+1,c+n+1)-c-1; rep(i,1,n)op[i].b=lower_bound(c+1,c+num+1,op[i].b)-c; rep(i,1,n) { if(op[i].a[0]==‘B‘)add((int)op[i].b,1); else if(op[i].a[0]==‘D‘)add((int)op[i].b,-1); else ans+=min(op[i].c,get(num)-get((int)op[i].b-1)); } printf("%.2f\n",(double)ans/100); //system("Pause"); return 0; }
原文：http://www.cnblogs.com/dyzll/p/5831082.html