A - Candy Button

洛谷链接

题目

代码

#include <bits/stdc++.h>

using namespace std;

int n, c, a, cnt = 1, x;

int main()
{
	scanf("%d %d\n%d", &n, &c, &x);
	for (int i = 1; i < n; i ++ )
	{
		scanf("%d", &a);
		if (a - x >= c)
		{
			cnt ++;
			x = a;
		}
	}
	cout << cnt << '\n';
	return 0;
}

B - Hands on Ring (Easy)

洛谷链接

题目

• 将其中一只手移动到当前所持部件的相邻部分。但是，只有当另一只手不在目标部件上时才能这样做。

• 执行一定数量的操作（可能为零），使您的左手（如果 $H_i$ 为 L）或右手（如果 $H_i$ 为 R）握住 $T_i$ 部分。在此，您不得移动 $H_i$ 未指定的手。

思路

• 给你一个整数 $from,to$ 和 $ng$，每个整数都在 $1$ 和 $N$ 之间。从 $from$ 部分到 $to$ 部分的循环需要走多少步？不经过部分 $ng$？（保证 $from \ne ng$ 和 $to \ne ng$）。

代码

#include <bits/stdc++.h>

using namespace std;

int n, q, l = 1, r = 2, ans, t;
char h;

int num_move(int n, int from, int to, int ng)
{
	if (from > to)
		swap(from, to);
	if (from < ng and ng < to)
		return n + from - to;
	else
		return to - from;
}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i = 0; i < q; i ++ )
	{
		cin >> h;
		scanf("%d", &t);
		if (h == 'L')
		{
			ans += num_move(n, l, t, r);
			l = t;
		}
		else
		{
			ans += num_move(n, r, t, l);
			r = t;
		}
	}
	cout << ans << '\n';
	return 0;
}

C - Prepare Another Box

洛谷链接

题目

1. 选择一个任意正整数 $x$ 并购买一个大小为 $x$ 的盒子。
2. 将每个 $N$ 玩具放入 $N$ 盒中（现有的 $N-1$ 盒加上新买的盒子）。在这里，每个玩具只能放进一个大小不小于该玩具大小的盒子里，任何盒子都不能装两个或两个以上的玩具。

思路

将 $A$ 按升序排序，得到 $a=(a_1,a_2, \ldots ,a_N)$。将 $x$ 插入 $B$，并按升序排序，得到 $b=(b_1,b_2, \ldots ,b_N)$。那么当且仅当 $a_i \le b_i$ 代表所有的 $i(1 \le i \le N)$ 时，步骤 $2$ 才是可行的。

• 充分性显而易见，因此我们将证明必要性：“如果第 $2$ 步可行，则所有 $i(1 \le i \le N)$ 均为 $a_i \le b_i$。”
• 将玩具和盒子重新编号，这样 $a_i$ 对应的玩具称为玩具 $i$，$b_i$ 对应的盒子称为盒子 $i$。当第 $2$ 步可行时，存在一个 $(1,2 \ldots ,N)$ 的排列 $p=(p_1,p_2, \ldots ,p_N)$，使得“所有 $i(1 \le i \le N)$ 都是 $a_i \le b_{p_i}$”。
• 假设存在 $i(1 \le i<N)$ 与 $p_i>p_{i+1}$。那么我们有 $a_i \le a_{i+1} \le b_{p_{i+1}} \le b_{p_i}$，因此有 $a_i \le b_{p_{i+1}}$ 和 $a_{i+1} \le b_{p_i}$；那么在交换 $p_i$ 和 $p_{i+1}$ 之后，仍然成立。当 $i(1 \le i<N)$ 与 $p_i>p_{i+1}$ 同时存在时，重复这一操作，就可以得到 $p=(1,2, \ldots ,N)$，同时保持。当 $p=(1,2, \ldots ,N)$ 存在时，表示所有 $i(1 \le i \le N)$ 的 $a_i \le b_i$，这正是我们想要的结果。

1. 假设玩具 $i$ 和盒子 $j$ 分别是最大的剩余玩具和盒子。
2. 如果 $A_i \le B_j$：将玩具 $i$ 放入盒子 $j$ 是最优选择。从玩具集合中删除玩具 $i$，从盒子集合中删除盒子 $j$；返回第 $1$ 步。
3. 如果 $A_i>B_j$：你无法将玩具 $i$ 放入任何一个剩余的盒子中，因此你需要购买一个大小至少为 $A_i$ 的新盒子。购买一个大小超过 $A_i$ 的盒子是没有用的，因此设置 $x=A_i$ 来应用上述标准。如果符合，则答案为 $A_i$；否则为 $-1$。

1. 将 $A$ 和 $B$ 按升序排序。
2. 如果存在 $i(1 \le i \le N-1)$ 与 $A_i>B_i$：答案为 $-1$。
3. 否则：答案为 $A_{i'+1}$，其中 $i'$ 是 $i(1 \le i \le N-1)$ 与 $A_{i+1}>B_i$ 的最大值（或 $0$，如果什么都不适用）。

代码

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
	scanf("%d", &n);
	vector<int> a(n), b(n - 1);
	for (int &i : a)
		scanf("%d", &i);
	for (int &i : b)
		scanf("%d", &i);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	for (int i = 0; i < n - 1; i ++ )
	{
		if (a[i] > b[i])
		{
			puts("-1");
			return 0;
		}
	}
	for (int i = n - 2; i >= 0; i -- )
	{
		if (a[i + 1] > b[i])
		{
			cout << a[i + 1] << '\n';
			return 0;
		}
	}
	cout << a[0] << '\n';
	return 0;
}