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; }
上一篇: 数据结构与算法知识架构总述
下一篇: Parallels Desktop的安装