- Plants vs. Zombies
- Time Limit: 2 Seconds Memory Limit: 65536 KB
BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao's zombies.
- Plants vs. Zombies(?)
- (Image from pixiv. ID: 21790160; Artist: socha)
- There are plants in DreamGrid's garden arranged in a line. From west to east, the plants are numbered from 1 to and the -th plant lies meters to the east of DreamGrid's house. The -th plant has a defense value of and a growth speed of . Initially, for all .
- DreamGrid uses a robot to water the plants. The robot is in his house initially. In one step of watering, DreamGrid will choose a direction (east or west) and the robot moves exactly 1 meter along the direction. After moving, if the -th plant is at the robot's position, the robot will water the plant and will be added to . Because the water in the robot is limited, at most steps can be done.
The defense value of the garden is defined as . DreamGrid needs your help to maximize the garden's defense value and win the game.
- Please note that:
- Each time the robot MUST move before watering a plant;
- It's OK for the robot to move more than meters to the east away from the house, or move back into the house, or even move to the west of the house.
- Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
- The first line contains two integers and (, ), indicating the number of plants and the maximum number of steps the robot can take.
- The second line contains integers (), where indicates the growth speed of the -th plant.
It's guaranteed that the sum of in all test cases will not exceed .
- Output
- For each test case output one line containing one integer, indicating the maximum defense value of the garden DreamGrid can get.
- Sample Input
- 2
- 4 8
- 3 2 6 6
- 3 9
- 10 10 1
- Sample Output
- 6 4
- Hint
- In the explanation below, 'E' indicates that the robot moves exactly 1 meter to the east from his current position, and 'W' indicates that the robot moves exactly 1 meter to the west from his current position.
- For the first test case, a candidate direction sequence is {
- E, E, W, E, E, W, E, E
- }, so that we have after the watering.
- For the second test case, a candidate direction sequence is {
- E, E, E, E, W, E, W, E, W
- }, so that we have after the watering.
- Author:WANG, Yucheng; CHEN, Shihan
- Source:The 2018 ACM-ICPC Asia Qingdao Regional Contest
[题意]
从左到右依次是 1 个房子 + n 个植物, 从房子出发给 n 个植物浇水, 每一次可以往左可以往右, 起始时植物的防御值都为 0, 每一次在 i 位置浇一次水, 防御增加 d[i], 每一次必须走, 不能呆在原地, 可以走出去, 定义 n 个植物的防御力为 min(ai),1<=i<=n, 问怎样走使得这些植物防御力最小值最大
[分析]
l=0,r=1e12 二分可以的最小价值的最大值. 以第一个样例为准, a[1]=3 a[2]=2 a[3]=6 a[4]=6 如果最小值为 7, 那么位置 1 就需要走 3 次, 即走到 2, 走回 1, 走到 2, 走回 1. 所以当 1 位置被走了 3 次后, 2 位置其实已经被走过了 2 次. 以此类推, 用 step 记录走的步数, 先算出在某个二分的值下每个位置最少需要走几步, 然后遍历一遍, 看看真实走的步数是否比 m 小, 如果小, 说明当前二分的值偏小, 否则偏大
[代码]
- #include<cstdio>
- using namespace std;
- typedef long long ll;
- inline ll read(){
- register char ch=getchar();register ll x=0;
- for(;ch<'0'||ch>'9';ch=getchar());
- for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
- return x;
- }
- const int N=1e5+5;
- int T,n;ll m,a[N],c[N],d[N];
- inline bool check(ll now){
- if(!now) return 1;
- ll tot=m;
- for(int i=1;i<=n;i++) c[i]=(now-1)/a[i]+1,d[i]=0;
- // 简洁化 if(now%a[i]) c[i]=now/a[i]+1;else c[i]=now/a[i];
- for(int i=1;i<=n;i++){
- if(i==n&&c[i]<=d[i]) return 1;
- if(tot<=0) return 0;
- d[i]++,tot--;
- if(c[i]<=d[i]) continue;
- ll need=c[i]-d[i];
- if((need<<1)>tot) return 0;
- tot-=need<<1;// 因为想让当前位置满足次数的话, 必定是一来一回, 需要两倍的步数
- d[i+1]+=need;//d[i] 对 d[i+1] 的贡献
- }
- return 1;
- }
- int main(){
- for(T=read();T--;){
- n=read();m=read();
- for(int i=1;i<=n;i++) a[i]=read();
- ll l=0,r=1e12,ans=0;
- while(l<=r){
- ll mid=l+r>>1;
- if(check(mid)){
- ans=mid;
- l=mid+1;
- }
- else{
- r=mid-1;
- }
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2931759.html