AtCoder Beginner Contest 376 A~C

IronMen · 2024-12-01 22:09:17 · 题解

A - Candy Button

洛谷链接

AtCoder链接

题目

有一个按钮，按下这个按钮时，你会得到一颗糖果，每次得到糖果的时间距离你上次得到糖果的时间大于等于 C 秒。

高桥决定按这个按钮 N 次。他将在 T_i 秒后按下 i 次按钮。

他会得到多少颗糖果？

代码

#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)

洛谷链接

AtCoder链接

题目

注：本问题的设置与问题 F 几乎相同，只有正文中粗体部分和限制条件不同。

你用双手拿着一个戒指。这个戒指由编号为 1,2, \ldots ,N 的 N(N \ge 3) 部分组成，其中 i 和 i+1(1 \le i \le N-1) 部分相邻，而 1 和 N 部分也相邻。

最初，您的左手拿着部件 1，右手拿着部件 2。在一次操作中，您可以完成以下操作：

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

下图显示了初始状态以及可以和不可以进行的操作示例。写在圆环各部分上的数字代表零件编号，标有 L 和 R 的圆圈分别代表你的左手和右手。

你需要按照 Q 的指示依次进行。第 i(1 \le i \le Q) 次指令由字符 H_i 和整数 T_i 表示，意思如下：

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

保证只给出可实现的指令。

求遵循所有指令所需的最小运算总数。

思路

按顺序扫描 Q 指令，同时管理您左右手的当前位置以及到目前为止所需的最少操作次数。对位置的管理非常简单，主要的工作是执行一个程序来响应以下类型的查询：

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

这个问题可以根据 from,to 和 ng 的排序来解决。三个整数有六种可能的排序，因此我们可以考虑每种排序；但是可以通过如下方式将其简化为两种排序，从而简化执行。

首先，我们可以自由交换 from 和 to（从 from 到 to 所需的步数等于从 to 到 from 所需的步数)。这样，如果有 from>to，我们就可以将 from 和 to 对调，从而始终有 from \le to。（这种通过固定排序来减少个案工作的技巧通常很有效）。

剩下的就是 ng 的位置，但基本上有两种情况：from<ng<to，以及其他情况。

对于前者，最佳的下法是 from \to (from-1) \to \cdots \to 1 \to N \to \cdots \to(to+1) \to to，需要 (from-1)+1+(N-to)=N+from-to 步。

对于后者，最佳移动方式是 from \to (from+1) \to \cdots \to (to-1) \to to，需要 to-from 步。

这样，解决问题总共只需 O(N) 步。

代码

#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

洛谷链接

AtCoder链接

题目

有 N 个玩具，编号从 1 到 N，有 N-1 个盒子，编号从 1 到 N-1。玩具 i(1 \le i \le N) 的大小为 A_i，盒子 i(1 \le i \le N-1) 的大小为 B_i。

高桥想把所有玩具分别存放在不同的盒子里，他决定按以下步骤依次进行：

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

他想通过在步骤 1 中购买一个足够大的盒子来执行步骤 2，但是大盒子的价格更高，所以他想购买尽可能小的盒子。

请判断是否存在一个 x 的值，使他可以执行步骤 2，如果存在，求这样的 x 的最小值。

思路

让我们首先考虑一下，当我们确定新购买的箱子的大小为 x 时，如何确定步骤 2 是否可行。

总之，可以使用下面的命题：

将 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，这正是我们想要的结果。

因此，根据这个条件，我们可以使用二进制搜索找到满足条件的最小值 x。如果对每个决策的序列 a 和 b 进行排序，总共需要花费 O(N \log (\max A_i)\log N)，这可以在时间限制内完成；也可以调整优化为 O(N \log (\max A_i))。

我们也可以不用二进制搜索，而用下面的贪心算法来解决这个问题。（有效性来自上面对固定 x 的讨论。）复杂度为 O(N \log N)，其中排序是瓶颈。

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。

通过观察这个贪心算法的行为，我们可以得出一个更简单的算法，如下所示。复杂度仍为 O(N \log N)。

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