JZOI5245 Competing Souls

0
11

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

JZOI5245

<

发布回复

请输入评论!
请输入你的名字