Monster
【题目描述】
明明的手机上有这样一个游戏,有一排n个怪物,每个怪物的血量是mi。现在明明可以射出k个伤害均为p的火球射向某些怪物。当某个火球射到第i个怪物,除了这个怪物会掉血p以外,它左边的第j个怪物(j<=i),也会遭到Max(0, p - (i - j)* (i - j))的溅射伤害。当某个怪物的血量为负的时候,它就死了,但它的尸体已然存在,即其他怪物不会因为它死而改变位置。
明明想用这k 个火球消灭掉所有的怪物,但他同时希望每个火球的伤害p能尽可能的小,这样他才能完美过关。
【输入数据】
第一行两个数 n, k (1≤ n ≤ 50000, 1 ≤ k ≤ 100000)。
第二行n个数m1, m2,...mn (1 ≤ mi ≤ 109),表示每个怪物的生命值。
【输出数据】
最小的符合要求的p值。
【样例输入】
3 1
1 4 5
【样例输出】
6
【数据范围】
1 ≤ n ≤ 50000, 1 ≤ k ≤100000,1 ≤ mi ≤109
30%的数据,n ≤ 500
贪心+二分 显然 最右边那个妖怪一定是被轰击致死的
Program monster;
const
INF=1000000000;
var
n,k,i,j:longint;
m1,a:array[1..50000] of longint;
procedure sort(l,r:longint);
var
i,j,m,k2,kn:longint;
begin
if l=r then
begin
writeln(l);
close(input);
close(output);
halt;
end;
m:=(l+r) shr 1;
for i:=1 to n do a[i]:=m1[i];
k2:=k;
for i:=n downto 1 do
if a[i]>0 then
begin
kn:=k2;
dec(k2,a[i] div m);
a[i]:=a[i] mod m;
if a[i]>0 then
begin
dec(k2);
dec(a[i],m);
end;
if k2<0 then sort(m+1,r);
kn:=kn-k2;
j:=i-1;
while (m-sqr(i-j)>0) and (j>=1) do
begin
if (kn*(a[j]-m+sqr(i-j))<0) then a[j]:=0 else
dec(a[j],kn*(m-sqr(i-j)));
dec(j);
end;
end;
sort(l,m);
end;
begin
assign(input,'monster.in');
assign(output,'monster.out');
reset(input);
rewrite(output);
read(n,k);
for i:=1 to n do
begin
read(m1[i]);
inc(m1[i]);
end;
sort(1,inf+1);
end.