首页 > 代码库 > sgu Ice-cream Tycoon

sgu Ice-cream Tycoon

2024-07-16 15:43:32   217人阅读

题意：供应商提供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         else116         {117             if(tree[1].num<p[i].n) printf("UNHAPPY\n");118             else119             {120                 if(search1(1,p[i].n)>p[i].w) printf("UNHAPPY\n");121                 else122                 {123                     printf("HAPPY\n");124                     change(1,p[i].n);125                 }126             }127         }128     }129     return 0;130 }
View Code

 


联系
我们