sgu Ice-cream Tycoon

题意：供应商提供n块价格为c的冰淇淋，一个学生想买n块冰淇淋，手中的钱数总共有t元，为了不让买n块冰淇淋所花费的钱数不超过t元，先尽可能卖给这个学生便宜的冰淇淋。

如果这个学生不能买到所需要的冰淇淋则输出“UNHAPPY”，能则输出“HAPPY”。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 200000
  5 using namespace std;
  6 
  7 long long x[maxn];
  8 struct node1
  9 {
 10     char str[100];
 11     int n;
 12     long long w;
 13 }p[maxn];
 14 struct node
 15 {
 16     int l,r;
 17     long long num;
 18     long long sum;
 19     int flag;
 20 }tree[maxn*4];
 21 
 22 void up(int i)
 23 {
 24     if(tree[i].l==tree[i].r) return ;
 25     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 26     tree[i].num=tree[i<<1].num+tree[i<<1|1].num;
 27 }
 28 void down(int i)
 29 {
 30     if(tree[i].l==tree[i].r) return ;
 31     if(tree[i].flag!=-1)
 32     {
 33         tree[i<<1].sum=tree[i<<1|1].sum=0;
 34         tree[i<<1].num=tree[i<<1|1].num=0;
 35         tree[i<<1].flag=tree[i<<1|1].flag=0;
 36         tree[i].flag=-1;
 37     }
 38 }
 39 
 40 void build(int i,int l,int r)
 41 {
 42     tree[i].l=l; tree[i].r=r;
 43     tree[i].num=tree[i].sum=0;
 44     tree[i].flag=-1;
 45     if(l==r) return ;
 46     int mid=(l+r)>>1;
 47     build(i<<1,l,mid);
 48     build(i<<1|1,mid+1,r);
 49 }
 50 
 51 void deal(int i,int n,int c)
 52 {
 53     tree[i].sum+=(long long)c*n;
 54     tree[i].num+=n;
 55     if(x[tree[i].l]==c&&x[tree[i].r]==c) return ;
 56     down(i);
 57     if(c<=x[tree[i<<1].r]) deal(i<<1,n,c);
 58     else deal(i<<1|1,n,c);
 59 }
 60 
 61 long long search1(int i,int n)
 62 {
 63     if(tree[i].l==tree[i].r)
 64     {
 65         return (long long)n*x[tree[i].l];
 66     }
 67     down(i);
 68     if(tree[i<<1].num>=n)  return search1(i<<1,n);
 69     else
 70         return tree[i<<1].sum+search1(i<<1|1,n-tree[i<<1].num);
 71 }
 72 
 73 void change(int i,int n)
 74 {
 75     if(tree[i].l==tree[i].r)
 76     {
 77         tree[i].num-=n;
 78         tree[i].sum=tree[i].num*x[tree[i].l];
 79         return ;
 80     }
 81     down(i);
 82     if(tree[i<<1].num>=n)
 83     {
 84         change(i<<1,n);
 85     }
 86     else
 87     {
 88         change(i<<1|1,n-tree[i<<1].num);
 89         tree[i<<1].num=0;
 90         tree[i<<1].sum=0;
 91         tree[i<<1].flag=0;
 92     }
 93     up(i);
 94 }
 95 int main()
 96 {
 97     int cnt=0,t1=0;
 98     while(scanf("%s %d%I64d",p[cnt].str,&p[cnt].n,&p[cnt].w)==3)
 99     {
100         if(p[cnt].str[0]=='A')
101         {
102             x[t1++]=p[cnt].w;
103         }
104         cnt++;
105     }
106     sort(x,x+t1);
107     t1=unique(x,x+t1)-x;
108     build(1,0,t1-1);
109     for(int i=0; i<cnt; i++)
110     {
111         if(p[i].str[0]=='A')
112         {
113             deal(1,p[i].n,p[i].w);
114         }
115         else
116         {
117             if(tree[1].num<p[i].n) printf("UNHAPPY
");
118             else
119             {
120                 if(search1(1,p[i].n)>p[i].w) printf("UNHAPPY
");
121                 else
122                 {
123                     printf("HAPPY
");
124                     change(1,p[i].n);
125                 }
126             }
127         }
128     }
129     return 0;
130 }

View Code