题解：P13674 [GCPC 2023] Investigating Frog Behaviour on Lily Pad Patterns

· · 题解

思路

本题可以采用 set。

首先，预处理初始位置和已被占用的荷叶。随后，排查出所有空荷叶的位置，只要某个荷叶尚未被占用，就将其临时存入空荷叶 set 中。

每当有查询请求时，先定位到青蛙当前所在的位置，再去寻找距离最近的空荷叶 —— 具体来说，就是找出第一个坐标值大于青蛙当前坐标的空荷叶。当新的坐标被占用后，原来的坐标就会被加入到空荷叶集合里（有涉及一点贪心思想）。

需要注意的是，要定期对池塘的荷叶进行扩展，这样才能避免后续青蛙出现没有地方可去的情况。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int X = 1e6 + 5;
int pos[N];
set<int> filled, gaps;
int m, t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> pos[i];
        filled.insert(pos[i]);
    }
    int maxp = pos[m];
    for (int i = 1; i <= maxp + 1; ++i) {
        if (!filled.count(i)) {
            gaps.insert(i);
        }
    }
    cin >> t;
    while (t--) {
        int idx;
        cin >> idx;
        int cur = pos[idx];
        auto it = gaps.upper_bound(cur);
        int nxt = *it;
        filled.erase(cur);
        filled.insert(nxt);
        gaps.erase(nxt);
        gaps.insert(cur);
        pos[idx] = nxt;
        if (gaps.upper_bound(nxt) == gaps.end()) {
            gaps.insert(nxt + 1);
        }
        cout << nxt << '\n';
    }
    return 0;
}