V - Ice-cream Tycoon(线段树) - c++编程基础

TOP

V - Ice-cream Tycoon(线段树)

2015-07-20 17:50:25 来源: 作者: 【大中小】浏览:1次

有两种操作，ARRIVE a b 表示单价为b的冰激凌的进货数目为a，BUY a b表示同学共拿b元钱，想买a个尽量便宜的冰激凌，若能购买到，输出HAPPY，否则输出UNHAPPY”

操作挺简单，单点更新然后push_up。但是写起来感觉挺麻烦。

首先先读入所有的操作，将进货的冰激凌单价离散化，建立线段树，然后按读入顺序，对于ARRIVE操作，更新相应的冰激凌的数目及价格，对“BUY操作，优先搜索左子树，即尽量买便宜的，若能购买，再去更新相应区间的数目及价钱。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #define LL long long #define eps 1e-12 #define PI acos(-1.0) #define PP pair
               
                 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100010; const int mod = 1000000007; struct Info { char str[10]; LL num; LL mon; } info[maxn]; struct node { int l,r; LL num; //冰激凌数目 LL sum;//总价钱 LL price;//一种冰激凌的单价 } tree[maxn*4]; LL x[maxn]; int Binsearch(int l, int r, LL key) { int mid,low = l,high = r; while(high >= low) { mid = (low + high) >> 1; if(x[mid] == key) return mid; if(x[mid] > key) high = mid - 1; else low = mid + 1; } return -1; } void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].num = tree[v].sum = tree[v].price = 0; if(l == r) return; int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } void push_down(int v) { if(tree[v].l == tree[v].r) return; if(tree[v].num == 0 && tree[v].sum == 0) { tree[v*2].num = tree[v*2+1].num = 0; tree[v*2].sum = tree[v*2+1].sum = 0; } } void push_up(int v) { tree[v].num = tree[v*2].num + tree[v*2+1].num; tree[v].sum = tree[v*2].sum + tree[v*2+1].sum; } void update(int v, int pos, LL num, LL mon, LL t) { if(tree[v].l == tree[v].r) { if(tree[v].price == 0) tree[v].price = mon; tree[v].num += num; tree[v].sum += t; return; } push_down(v); //重点，不要遗漏。 int mid = (tree[v].l + tree[v].r)>>1; if(pos <= mid) update(v*2,pos,num,mon,t); else update(v*2+1,pos,num,mon,t); push_up(v); } void update_1(int v, LL num, LL sum) { tree[v].num -= num; tree[v].sum -= sum; if(tree[v].l == tree[v].r) return; if(tree[v*2].num >= num) update_1(v*2,num,sum); else { LL tmp1 = num - tree[v*2].num; LL tmp2 = sum - tree[v*2].sum; tree[v*2].num = 0; tree[v*2].sum = 0; update_1(v*2+1,tmp1,tmp2); } } LL query(int v, LL num) { if(tree[v].num < num) return -1; if(tree[v].num == num) { return tree[v].sum; } if(tree[v].l == tree[v].r) { return tree[v].price * num; } if(tree[v*2].num >= num) return query(v*2,num); else { LL res = query(v*2+1,num-tree[v*2].num); return tree[v*2].sum + res; } } int main() { int t1,t2,k; LL a,b; char ch[10]; t1 = 0; t2 = 0; while(~scanf(%s %I64d %I64d,ch,&a,&b)) { struct Info tmp; strcpy(tmp.str,ch); tmp.num = a; tmp.mon = b; info[++t1] = tmp; if(ch[0] == 'A') x[++t2] = b; } sort(x+1,x+1+t2); k = 1; for(int i = 2; i <= t2; i++) { if(x[i] != x[i-1]) x[++k] = x[i]; } build(1,1,k); for(int i = 1; i <= t1; i++) { if(info[i].str[0] == 'A') { int pos = Binsearch(1,k,info[i].mon); LL t = info[i].num*info[i].mon; update(1,pos,info[i].num,info[i].mon,t);//单点更新冰激凌的数目，价格和单价 } else { LL res = query(1,info[i].num); if(res == -1) //总数目小于购买数目 printf(UNHAPPY ); else { if(info[i].mon >= res) { printf(HAPPY ); update_1(1,info[i].num,res);//能购买，就去更新相应区间的数目及价钱 } else printf(UNHAPPY ); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 3169 Layout (差分约束+Bellm..	下一篇：uva116 - Unidirectional TSP(记..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: