Watermelon

在ACM队暑假集训的某一天，实验室里有 $\ n$ 个人。因为天气很热，大家都很想吃西瓜。
于是Eric买了 $\ m$ 个西瓜拿到了实验室。
Eric把这 $\ n$ 个人分别编号为 $\ 1,2,3...n$ ,他希望这 $\ n$ 个人循环轮流来吃西瓜。
也就是说从 $\ 1$ 号开始，然后 $\ 2$ 号， $\ 3$ 号... $\ n$ 号依次吃西瓜， $\ n$ 号吃完后又轮到 $\ 1$ 号来吃，直到这 $\ m$ 个西瓜被吃完。
而这 $\ n$ 个人每个人有一个肚量值，第i个人的肚量值为 $\ a_{i}$ 。
lililalala是这 $\ n$ 个人肚量值最大的人，不仅如此，他还非常贪吃，每次轮到他吃西瓜时，都会直接吃掉等同于他的度量值数量的西瓜。如果剩余的西瓜已经不够吃了，那么他会把所有西瓜直接吃完。(是的他很能吃)
除了lililalala以外的其他人,对于第 $\ i$ 号每次吃西瓜可以选择吃掉 $\ [1,a_{i}]$ 中任意整数数量个西瓜。当然，不能超过当前剩余的西瓜数量。
为了使吃西瓜更有意思一些，Eric规定如果在轮到某个人吃西瓜时没有西瓜了，那么由他来打扫一次实验室。(是的大家都很能吃)
其他人都觉得lililalala吃的太多了应该由他来打扫卫生。请问在其他人串通好的情况下能否合理安排每个人的行动使得吃完西瓜后由lililalala来打扫卫生?

第一行一个数字 $T(1 \le T \le 50)$ --样例个数。
每个样例包含两行。
第一行两个数字 $n,m(1 \le n \le 10^{5},0 \le m \le 10^{6})$ 。
第二行 $\ n$ 个数字 $a_{1},a_{2}...a_{n}(1 \le ai \le 10^{7})$ ，以空格分隔。
保证所有样例中肚量最大的人只有一个。这个人是lililalala。
保证所有样例中 $\ \sum n$ 不超过 $\ 3 \times 10^{6}$ 。
保证所有样例中 $\ \sum m$ 不超过 $\ 10^{7}$ 。

#include<bits/stdc++.h> using namespace std; int a[100005]; int main(){ int T; scanf("%d",&T); while(T--){ int n,m; int mx=0; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d",&a[i]); if(a[i]>a[mx]) mx=i; } int l=m,r=m,t=-1; while(1){ t++; t%=n; if(mx==t){ if(r<=0) break; l-=a[t]; r-=a[t]; } else{ if(l<=0) break; l-=1; r-=a[t]; } } if(t!=mx) puts("NO"); else puts("YES"); } }

#include<bits/stdc++.h> #define ll long long using namespace std; ll t,a[100000],s[100000]; int main(){ cin>>t; while(t--){ s[0]=0; ll n,m,p=1,l,r; cin>>n>>m; for(ll i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; if(a[i]>a[p])p=i; } if(n==1){printf("YES\n");continue;} l=p-1;r=s[p-1]; while(r<m) { r+=s[n]; l+=n-1+a[p]; } if(m>=l&&m<=r)printf("YES\n"); else printf("NO\n"); } }

详情