欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JZOI5245 Competing Souls

程序员文章站 2022-03-26 14:46:00
Description 某日,竞赛班的学生来到了一家糖果店。 店里卖着M袋糖果,第i袋糖果里装有i颗糖,价格为i¥。 有N个学生对这些糖果产生了兴趣,于是迅速站成一排,且将他们编号为1到N。其中第i个学生带着a[i]¥。每一轮,他们按顺序买糖果(每一轮每个人只会买一袋)。由于体内的竞争之魂与超乎常人 ......

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;
}