JZOI5245 Competing Souls

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\n",ans);
    }
    return 0;
}