E.Watermelon（思维）

2024-03-19 17:18

文章标签 思维 watermelon

本文主要是介绍E.Watermelon（思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2019年湘潭大学程序设计竞赛（重现赛）补题：
链接：https://ac.nowcoder.com/acm/contest/893/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
在ACM队暑假集训的某一天，实验室里有\ n n个人。因为天气很热，大家都很想吃西瓜。
于是Eric买了\ m m个西瓜拿到了实验室。
Eric把这\ n n个人分别编号为\ 1,2,3…n 1,2,3…n,他希望这\ n n个人循环轮流来吃西瓜。
也就是说从\ 1 1号开始，然后\ 2 2号，\ 3 3号… \ n n号依次吃西瓜，\ n n号吃完后又轮到\ 1 1号来吃，直到这\ m m个西瓜被吃完。
而这\ n n个人每个人有一个肚量值，第i个人的肚量值为\ a_{i} a
i

。
lililalala是这\ n n个人肚量值最大的人，不仅如此，他还非常贪吃，每次轮到他吃西瓜时，都会直接吃掉等同于他的度量值数量的西瓜。如果剩余的西瓜已经不够吃了，那么他会把所有西瓜直接吃完。(是的他很能吃)
除了lililalala以外的其他人,对于第\ i i号每次吃西瓜可以选择吃掉\ [1,a_{i}] [1,a
i

]中任意整数数量个西瓜。当然，不能超过当前剩余的西瓜数量。
为了使吃西瓜更有意思一些，Eric规定如果在轮到某个人吃西瓜时没有西瓜了，那么由他来打扫一次实验室。(是的大家都很能吃)
其他人都觉得lililalala吃的太多了应该由他来打扫卫生。请问在其他人串通好的情况下能否合理安排每个人的行动使得吃完西瓜后由lililalala来打扫卫生?
输入描述:
第一行一个数字T(1 \le T \le 50)T(1≤T≤50)–样例个数。
每个样例包含两行。
第一行两个数字n,m(1 \le n \le 10^{5},0 \le m \le 10^{6})n,m(1≤n≤10 5 ,0≤m≤10 6 )。
第二行\ n n个数字a_{1},a_{2}…a_{n}(1 \le ai \le 10^{7})a 1,a 2…a n (1≤ai≤10 7 )，以空格分隔。
保证所有样例中肚量最大的人只有一个。这个人是lililalala。
保证所有样例中\ \sum n ∑n不超过\ 3 \times 10^{6} 3×10 6 。
保证所有样例中\ \sum m ∑m不超过\ 10^{7} 10 7 。
输出描述:
每个样例输出一行，输出”YES”如果合理安排可以使得最后由lililalala来打扫卫生，否则输出“NO”。
示例1
输入
复制

输出
复制

YES
NO

说明
第一个样例中lililalala是3号:
一种可行的方案:
1号吃掉1个西瓜
2号吃掉2个西瓜
第一次到3号吃西瓜时就没有西瓜可以吃了，所以3号需要打扫卫生。

第二个样例无论怎样安排各个人在每一次吃西瓜的数量，也不能达成目标。
/*
本题看似像博弈，其实可以说是一个模拟。
利用极限思维，维护一个当前消耗西瓜的最小值和最大值（l,r）
除了lililalala外，l+=1，表示其他人每次先吃一个西瓜，
对于r，遇到谁都是 r += a[i]，表示当前消耗的西瓜最大值
如果在lililalala之前r可以大于等于m（r >= m）,
那么就一定可以让lililalalalililalala没瓜吃。
如果在非lililalala时，l >= m,表示没轮到lililalala吃瓜，瓜就没了。
每次在更新l和r前判断当前情况从而得出答案。
*/

#include <iostream>
using namespace std;
typedef long long LL;
const LL MAXN = 1e5+5;
LL a[MAXN];
int main ()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;int maxx = 0,pos = 0;for(int i = 0; i < n; i++){cin>>a[i];if(a[i] > maxx){maxx = a[i];pos = i;}}if(n == 1){cout<<"YES"<<endl;continue;}LL l = 0,r = 0,flag = 0;while(flag == 0){for(int i = 0; i < n; i++){if(i != pos && l >= m){flag = -1;break;}if(i == pos && r >= m){flag = 1;break;}l += (i == pos ? a[i] : 1);r += a[i];}}if(flag == 1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}