AtCoder AT_abc412_c [ABC412C] Giant Domino 题解

题目大意

有 $N$ 个数，顺序可以打乱，第 $i$ 个数是 $S_i$。每次可以从第 $i$ 个数跳到第 $j$ 个数当且仅当满足 $S_j\le 2\cdot S_i$，问从第 $1$ 个数跳到第 $N$ 个数最少需要多少步。

思路

容易发现，每次跳到的数越大越好，这样答案才能最优。因为如果你跳到第 $x$ 个数后下一步可以跳到第 $k$ 个数，同时也可以跳到第 $y$ 个数且满足 $S_x\le S_y$，那么跳到第 $y$ 个数后一定也可以跳到第 $k$ 个数，所以显然是不劣的。对于满足 $S_x<S_y$ 的情况，如果存在 $S_z=2\cdot S_y$，那么第 $y$ 个数可以跳过去而第 $x$ 个数不可以。所以，我们优先跳到值更大的数。

由于可以打乱顺序，我们为了方便可以直接对这个数组进行从小到大排序，然后找到其中 $S_1$ 和 $S_N$ 的位置，分别记为 $l$ 和 $r$。如果某个数出现了多次也不影响计算答案，因为同一个值反复跳显然是不优的。如果满足 $S_1\ge S_N$ 的话，可以直接输出 2 并不再进行下列操作，否则会有十二个点答案错误。

数组具有单调性，我们从 $l$ 开始跳，每次用二分跳满足 $S_p\le 2\cdot S_l$ 且 $S_p$ 尽可能大的 $p$，然后将 $l$ 的值设为 $p$，统计数量，直到 $S_l$ 与 $S_r$ 相等为止。如果在过程中出现死循环（及 $S_p$ 和 $S_l$ 相等），则无解（输出 -1 并结束操作）。

代码

提交记录：Submission #67141171。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int t, n, s[200010];

int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> s[i];
		int sz1 = s[1], sz2 = s[n];
		sort(s + 1, s + n + 1);
		int l = upper_bound(s + 1, s + n + 1, sz1) - s - 1;
		int r = upper_bound(s + 1, s + n + 1, sz2) - s - 1;
		if (sz1 * 2 >= sz2)
		{
			cout << "2" << endl;
			continue;
		}
		int ans = 1;
		while (l != r && s[l] != s[r])
		{
			int p = upper_bound(s + l, s + r + 1, 2 * s[l]) - s - 1;
			if (p <= l || s[l + 1] > 2 * s[l])
			{
				ans = -1;
				break;
			}
			l = p;
			ans++;
		}
		cout << ans << endl;
	}
	return 0;
}