C. Doremy‘s IQ（贪心）

Problem

给出一个长度为n的序列a，按次序遍历。现在给出一个q，按次序对$a[i]$进行测试。测试时，执行以下操作：

• 如果 $q\ge a[i]$， q不变
• 如果 $q<a[i]$， $q=q-1$

可以跳过某个测试，q不发生变化。当q = 0时，终止。
问最多可以执行几次测试，输入最优方案的01序列。

Solution

首先考虑到前面执行测试会影响到后面的情况，所以就可以考虑反向思考。当然也可以正向思考，只不过正向思考比较麻烦。
方法一：正向思考，贪心+二分
方法二：逆向思考，贪心

One

那些会使q减小的操作应尽量靠后。
对于方案中的第一个使q减小的测试，其实可以将其调换到最后面的没有进行进行测试的一个位置。
不断执行上面的调换，直到该位置后面所有的都进行了测试。
该调换不会使得结果变小，只会使得结果更优。
最终会形成一个后缀。在后缀中，无论 $a[i]$ 的大小，都进行测试。
前面的部分，只有不会使q减小的进行测试。
最优方案应该使后缀尽量长。所以可以二分求解。

Two

逆向思考：假如q初始为0
为了让 会使q变小的测试尽量排在后面，
逆序遍历，如果 $a[i]>q$, q++。直到q 等于输入中q的值。
这之后，前面的只有 $a[i]\le q$ 才进行测试。

Code

这是方法一的代码（方法二代码很简单，就不写了）

bool check(int mid)
{
	int qq = q;
	for (int i = mid; i <= n; i++)
		if (a[i] > qq) qq--;

	return qq >= 0;
}

int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		cin >> n >> q;
		for (int i = 1; i <= n; i++) cin >> a[i];
		
		int l = 1, r = n;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (check(mid)) r = mid;//mid应该尽量小
			else l = mid + 1;//mid太小了，导致check中qq < 0
		}
		for (int i = 1; i <= n; i++)
			if (i < l) cout << (a[i] <= q ? 1 : 0);
			else cout << 1;
		cout << "\n";
	}


	return 0;
}
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