【Codeforces398A】Cards

题目大意:给出两个非负整数a,b (a+b>=1),你需要构造一个由a个o和b个x构成的序列。对于任何一个序列,我们可以算出一个分数:

初始分数为 0;

对于每一块o,设其长度为x,则分数加上x^2;

对于每一块x,设其长度为y,分数减去y^2。

要求构造出一个最大的序列。

那么我们可以发现,若把a个o分成k块,则最大的分数为1+1+1+…+(a-k+1)^2(不会证,想想就知道了)

那么要把b个x分成(k+1)块,分别插进k块o中,则要使减去的分数最小,就要使每一块的个数尽量平均。也就是每一块先有⌊b/(a-1)⌋个数,然后每一块加1直到分完。

枚举一下k,取分数最大值即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz