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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/38520.html
標籤：C++
上一篇：G++編譯鏈接的那些事!G++的特殊使用方法[常用]
下一篇：CreateEvent行程同步