1676：手机游戏
时间限制: 1000 ms 内存限制: 131072 KB
【题目描述】
明明的手机上有这样一个游戏，一排\(n\)个怪物，每个怪物的血量是\(m_i\)。现在明明可以射出k个伤害均为\(p\)的火球，当某个火球射到第\(i\)个怪物，除了这个怪物会掉血\(p\)以外，它左边的第\(j\)个怪物\((j≤i)\)，也会遭到\(max(0,p−(i−j)^2)\)的溅射伤害。当某个怪物的血量为负的时候，它就死了，但它的尸体依然存在，即其他怪物不会因为它死而改变位置。
明明想用这\(k\)个火球消灭掉所有的怪物，但他同时希望每个火球的伤害\(p\)能尽可能的小，这样他才能完美过关。
所有数均为整数。
【输入】
第一行两个数\(n,k\)。
第二行\(n\)个数\(m_1,m_2,…,m_n\)
表示每个怪物的生命值。
【输出】
一行一个整数表示最小的符合要求的\(p\)值。
【输入样例】
3 1
1 4 5
【输出样例】
6
【数据规模】
对于30%的数据，\(n≤500\)。
对于100%的数据，\(1≤n≤50000，1≤k≤100000，1≤mi≤10^9\)
二分答案。
问题在于题目要仔细读，j 的含意要认真体会！
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int n,sz[maxn],k,m[maxn];
bool pd(long long cur)
{
int pos=n;
for(int i=1;i<=k;++i)
{
m[pos]-=cur;
for(int j=1;pos-j>0&&cur-j*j>0;++j)m[pos-j]-=cur-j*j;
//for(int j=pos;j>0&&(pos-j)*(pos-j)<cur;--j)m[j]-=cur-(pos-j)*(pos-j);
while(m[pos]<0&&pos>0)pos--;
}
return pos==0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",&sz[i]);
long long l=0,r=2e9+1,ans;
while(l<=r)
{
long long cur=(l+r)>>1;
for(int i=1;i<=n;++i)m[i]=sz[i];
if(pd(cur))ans=cur,r=cur-1;
else l=cur+1;
}
cout<<ans<<endl;
return 0;
}