2018年ACM-ICPC亚洲青岛区域竞赛 - E - Plants vs. Zombies
Whiteying
2018-11-14 00:00:50
# A类
借鉴与：https://blog.csdn.net/BePosit/article/details/83929892
# 题目链接：
https://vjudge.net/problem/ZOJ-4062
# 题意：
看到题目以为是个非常复杂的题。
但显然题意和植物大战僵尸没有半毛钱关系（出题人过来我保证不打死你(╯‵□′)╯︵┻━┻）
## （真）题意（雾
你的房子在n点每个点都有一颗高度为0的花，浇一次水花会长a[i]。
你有一个机器人，刚开始在你家，最多走m步，每一步只能往前走或者往后走，每走到一个地方除了房子都会给花浇水，问m步以后最低那朵花的高度最大是多少。
# 思路：
最大化最小值，用二分的思想
从前往后计算每一朵花要满足答案需要浇多少次水。
------------
二分条件：left<right
二分计算：middle=（left+right+1）/2
二分转移：符合条件时left=middle，不符合条件时
right=middle-1
------------
对于一朵花达不到我们所需要的高度时，跟它右边那朵花那个反复跳即可。这样的话每一次二分判断，先预处理出实际应该遍历这个点几次
到达一个点时先sum++，因为第一次总是要从前面过来的，不是在后面循环过程中凑出来的
每次都是向右循环凑次数：
### sum+=(b[i]-1)*2
所以每一次需要走的次数应当减去上次循环过程中已经走过的
### b[i+1]-=(b[i]-1);
然后记录需要使用跳多少次即可。最后只需判断次数是否大于m即可
如果到了最后需要判断是否需要sum++
### if(i==n&&b[i]<1)break;
# AC代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
long long t,n,m;
long long maxx;
long long a[100005];
long long b[100005];
bool check(long long now)
{
long long sum=0;
for(int i=1;i<=n;i++)
{
if(now%a[i])
b[i]=now/a[i]+1;
else
b[i]=now/a[i];
}
for(int i=1;i<=n;i++)
{
if(i==n&&b[i]<1)
return true;
sum++;
if(b[i]>1)
{
sum+=(b[i]-1)*2;
b[i+1]-=(b[i]-1);
}
if(sum>m)
return false;
}
return true;
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
maxx=0;
for (int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(a[i]>maxx)
maxx=a[i];
}
maxx=maxx*m;
long long left=0,right=maxx,middle;
while(left<right)
{
middle=(left+right+1)/2;
if(check(middle))
left=middle;
else
right=middle-1;
}
printf("%lld\n",right);
}
return 0;
}
```