ZOJ - 4062

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 nnn plants in DreamGrid’s garden arranged in a line. From west to east, the plants are numbered from 1 to nnn and the iii-th plant lies iii meters to the east of DreamGrid’s house. The iii-th plant has a defense value of did_idi​ and a growth speed of aia_iai​. Initially, di=0d_i = 0di​=0 for all 1≤i≤n1 \le i \le n1≤i≤n.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 iii-th plant is at the robot’s position, the robot will water the plant and aia_iai​ will be added to did_idi​. Because the water in the robot is limited, at most mmm steps can be done.The defense value of the garden is defined as min⁡{di∣1≤i≤n}\min\{d_i | 1 \le i \le n\}min{di​∣1≤i≤n}. 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 nnn meters to the east away from the house, or move back into the house, or even move to the west of the house.InputThere are multiple test cases. The first line of the input contains an integer TTT, indicating the number of test cases. For each test case:The first line contains two integers nnn and mmm (2≤n≤1052 \le n \le 10^52≤n≤105, 0≤m≤10120 \le m \le 10^{12}0≤m≤1012), indicating the number of plants and the maximum number of steps the robot can take.The second line contains nnn integers a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​ (1≤ai≤1051 \le a_i \le 10^51≤ai​≤105), where aia_iai​ indicates the growth speed of the iii-th plant.It’s guaranteed that the sum of nnn in all test cases will not exceed 10610^6106.OutputFor 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 Output6
4
HintIn 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 d={6,6,12,6}d = \{6,6,12,6\}d={6,6,12,6} 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 d={10,10,4}d = \{10, 10, 4\}d={10,10,4} after the watering.

思路：这道题是求最小值的最大情况，可以考虑二分答案。我们对defense value进行二分。当defense value确定下来后，在确定m步之后能否满足当前的defense value，能满足说明答案要小于等于当前的defense value，否则就大于等于，相应进行二分即可。判断见代码注释。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdbool.h>
inline int min(int Left,int Right){
      return Left<Right?Left:Right;
}

int T;


long long n, m;
int Grow[200005];
long long Times[200005];

//判断m步能是高度全部大于high🐎
inline bool Judgt(const long long high) {

	//算出第i棵植物要浇几次水才能得到高度high
	for (long long i = 0; i < n; i++) {
		Times[i] = (high - 1) / Grow[i];
	}
	//加个虚点
	Times[n] = 0;
	//已经走的步数
	long long Step = n;

	for (int i = 0; i < n; i++) {
		//处理边界条件，即最后两个点
		//如果最后一个点次数大于倒数第二个，直接往下走。（有个次数为0的虚点）
		if (i == n - 2 && Times[i] > Times[i + 1]) {
			Step += (Times[i] << 1) - 1;
			if (Step > m) {
				return false;
			}
			break;
		}

		//在i和i+1反复横跳，所以乘2
		//先处理完局部的就不用重复走，是最优的
		Step += Times[i] << 1;
		//超出步数就说明条件无法满足
		if (Step > m) {
			return false;
		}
		//接下来判段i+1在反复横跳处理完i后还需浇水的次数
		else if (Times[i + 1] > Times[i]) {
			Times[i + 1] -= Times[i];
		}
		else {
			Times[i + 1] = 0;
		}
	}

	return true;

}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &m);
		long long Left = 0, Right;
		int Temp = 2000000000;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &Grow[i]);
			Temp = min(Temp, Grow[i]);
		}
		if (m < n) {
			puts("0");
			continue;
		}
		Right = Temp * (m-n+1);
		long long Ans =0;
		while (Left <= Right) {
			long long mid = (Left + Right + 1) >> 1;
			if (Judgt(mid)) {
				Ans = mid;
				Left = mid + 1;
			}
			else {
				Right = mid - 1;
			}
		}
		printf("%lld\n", Ans);
	}
	return 0;
}