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

· · 题解

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

题目概括

有一排睡莲，一些青蛙初始在一些睡莲上，每次给出第 i 只青蛙跳跃了，每个青蛙只会跳到右侧距离自己最近的空位，求每次跳跃后跳到的地方。

思路

可以想到将空位放到一个容器中，每次跳跃只需要找到容器中在这个青蛙右侧最小的位置，修改青蛙位置后将新的空位加入容器。这里有一个查找大于等于某数的最小值的操作，我们考虑使用 set 容器。并且位置不会重复，可以使用。

具体方法

在刚刚读入青蛙位置时，应当记录最后一个青蛙的位置 maxx，如果有一只青蛙不得已要跳到最后一只青蛙往后，可以直接跳到 maxx 的下一个睡莲上，并更新 maxx。

全部读入后，我们需要枚举每个区间（两端点为两个青蛙），并将区间内的位置（不含端点）加入空位的集合中。

接下来进行跳跃，当第 x 个青蛙跳跃了，先判断它的下一个位置有没有超过 maxx，即它是最后一只。若是，则直接跳到 maxx 的下一个位置。否则使用 lower_bound(a[x+1]) 查找大于等于此位置的下一个位置的最小空位。如果没找到，就只能跳到 maxx 的下一个位置了。

每次跳跃要删掉跳到的空位，并把之前的位置加入空位，输出答案即可。

代码

#include <bits/stdc++.h>
using namespace std;

int n,a[1000005],q;     //一定要开大点 

set<int> emp;

int main(){
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> a[i];
    }
    int maxx=a[n];
    for (int i=1;i<n;i++){
        int sta=a[i];
        int end=a[i+1];
        for (int j=a[i]+1;j<a[i+1];j++) emp.insert(j);      //加入空位 
    }
    cin >> q;
    for (int i=1;i<=q;i++){
        int x;
        cin >> x;
        int pos=a[x]+1;
        int npos;
        if (pos>maxx){      //是否是最后一个 
            npos=pos;
        }
        else{       //这里指针数据类型要注意 
            auto p=emp.lower_bound(pos);
            if (p!=emp.end()){
                npos=*p;
                emp.erase(p);
            }
            else{
                npos=maxx+1;
            }
        }
        emp.insert(a[x]);
        a[x]=npos;      //修改空位和位置 
        maxx=max(maxx,npos);        //修改最后一个青蛙 
        cout << npos << endl;       //输出答案 
    }
    return 0;
}

总结

因为我们需要找到比某数大的最小值，所以正好可以根据集合的单调性直接使用它的查找函数，选择正确的容器很重要。