Description
某日，竞赛班的学生来到了一家糖果店。
店里卖着M袋糖果，第i袋糖果里装有i颗糖，价格为i¥。
有N个学生对这些糖果产生了兴趣，于是迅速站成一排，且将他们编号为1到N。其中第i个学生带着a[i]¥。每一轮，他们按顺序买糖果（每一轮每个人只会买一袋）。由于体内的竞争之魂与超乎常人的不服输精神，当前学生买的这袋糖果一定会比上一个人多（当然，第一次可以随便买）。如果第N个人买了糖果，那么就到第1个人开始下一轮。
然而，钱和糖果都有限，总是要停下来的。可以在任意时刻停止购买糖果，但是最后一次必须是第N个人购买。
现在他们想知道，最终所有人购买糖果数之和最大可以是多少。（当然可以一袋都不买~）
Solution
直接考虑最大化糖果的方案比较困难，转化为用糖果最小的方案逐渐增加糖果直至不能增加。
假设：n=3，m=11，假设有3轮选择，则这三个人的选择方案组成的矩阵（称其为初始矩阵）为
1 2 3
4 5 6
7 8 9
其中第一列，第二列，第三列表示第一个人，第二个人，第三个人的选择，第一行，第二行，第三行表示第一轮，第二轮，第三轮选择。
发现可以把整行+1，从而让糖果数增加（在手里的钱允许的情况下），即
1 2 3
4 5 6
8 9 10
也有的时候手里的总钱数不允许把整行都+1，优先从第3个人开始增加糖果（后拿的人的糖果数>先拿的人的糖果数），即
1 2 3
4 5 6
7 9 10（第三行部分+1）
显然，让两行分别+1与让一行+2增加的糖果和钱数都是一样的，即两行+1与一行+2的效果相同，因为后拿的糖果>先拿的糖果，所以贪心策略为枚举拿糖的轮数，优先给靠后的行加糖果到最大，这之前的行优先从后拿的糖果开始到第一次拿的糖果增加到最大（要保证有足够的糖果和手里的钱足够）
那么设靠后的$h$行能够被一次加满，设每个人手里的钱数-初始矩阵中他选择的糖果的总价（即买了初始糖果后剩余的钱数）为$delta$，此时枚举到选择了$i$轮，则$h=min(frac{delta}{m-in},i)$（感性理解）（$m-in$为将一个糖果增加到可能的最大值所需增加的钱数）
1 2 3 1 2 3
4 5 6 ---> 4 5 6
7 8 9 9 10 11
在之前的$i-h$行中就逐个使其到达最大（注意保证后拿的糖果多与先拿的糖果）
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long t,n,m,a[5000005],ans,sum,delta,h,w[5000005]; inline long long read() { long long w=0,f=1; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return w*f; } int main() { t=read(); for(;t;t--) { ans=0; n=read(); m=read(); for(long long i=1;i<=n;i++) { a[i]=read(); } for(long long i=1;i<=m/n;i++) { sum=((1+i*n)*i*n)>>1; delta=(long long)1<<60; for(long long j=1;j<=n;j++) { a[j]-=i*n-n+j; delta=min(delta,a[j]); } if(delta<0) { break; } h=min(i,delta/(m-i*n)); sum+=h*n*(m-i*n); delta=h*(m-i*n); for(long long j=1;j<=n;j++) { w[j]=a[j]-delta; } delta=m-i*n; for(long long j=i-h;j>=i-h-1&&j;j--) { for(long long k=n;k;k--) { delta=min(delta,w[k]); w[k]-=delta; sum+=delta; if(!delta) { break; } } } ans=max(ans,sum); } printf("%lld ",ans); } return 0; }