首页 > 代码库 > Gym 101243E Cupcakes
Gym 101243E Cupcakes
http://codeforces.com/gym/101243/attachments
题意：
有n个人，桌子上有k的蛋糕，每个人都有一个值val，表示每次轮到他吃蛋糕时，他可以吃1~val的蛋糕量。在这n个人当中，val最大的人是最贪婪的，他每次都会固定的吃val蛋糕。现在一个一个排好队吃蛋糕，如果轮到谁吃蛋糕时已经没有蛋糕了，那么这个人就要打扫卫生，现在要判断是否能让最贪婪的人去打扫卫生。
思路：
先找出最贪婪的那个人，计算出他左边的人一轮下来所要吃的最少的蛋糕量l_min和最多的蛋糕了l_max，另外还要计算出一轮下来除贪婪人外其余人所要吃的最少的蛋糕了和最多的蛋糕量。
如果l_min<=k<=l_max，那么左边的人肯定能在轮到贪婪的人吃时正好吃完蛋糕。
如果不能的话，那么蛋糕就要被贪婪的人吃掉点，接下来我们加上一轮下来其余人所要吃的最少的蛋糕和最多的蛋糕，重复上述步骤判断。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 1e5+5;17 18 int n, k;19 ll a[maxn];20 21 int main()22 {23 freopen("input.txt","r",stdin);24 freopen("output.txt","w",stdout);25 //freopen("input.txt","r",stdin);26 while(~scanf("%d%d",&n,&k))27 {28 ll MAX=0;29 for(int i=1;i<=n;i++)30 {31 scanf("%lld",&a[i]);32 MAX=max(MAX,a[i]);33 }34 35 ll l_min=0, l_max=0;36 ll round_min=0, round_max=0;37 bool flag=true;38 39 for(int i=1;i<=n;i++)40 {41 if(a[i]==MAX) {flag=false;continue;}42 if(flag)43 {44 l_min++;45 l_max+=a[i];46 }47 round_min++;48 round_max+=a[i];49 }50 51 flag=false;52 while(k>=0)53 {54 if(k>=l_min && k<=l_max)55 {56 puts("YES");57 flag=true;58 break;59 }60 else61 {62 k-=MAX;63 l_min+=round_min;64 l_max+=round_max;65 }66 67 }68 if(!flag) puts("KEK");69 }70 return 0;71 }
Gym 101243E Cupcakes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。