专栏文章

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

yyytmcjs
P13674题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodmyax
此快照首次捕获于
2025/12/02 17:29
3 个月前
此快照最后确认于
2025/12/02 17:29
3 个月前
查看原文

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

题目概括

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

思路

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

具体方法

在刚刚读入青蛙位置时，应当记录最后一个青蛙的位置 maxxmaxx，如果有一只青蛙不得已要跳到最后一只青蛙往后，可以直接跳到 maxxmaxx 的下一个睡莲上，并更新 maxxmaxx。
全部读入后，我们需要枚举每个区间（两端点为两个青蛙），并将区间内的位置（不含端点）加入空位的集合中。
接下来进行跳跃，当第 xx 个青蛙跳跃了，先判断它的下一个位置有没有超过 maxxmaxx，即它是最后一只。若是，则直接跳到 maxxmaxx 的下一个位置。否则使用 lower_bound(a[x+1]) 查找大于等于此位置的下一个位置的最小空位。如果没找到，就只能跳到 maxxmaxx 的下一个位置了。
每次跳跃要删掉跳到的空位，并把之前的位置加入空位，输出答案即可。

代码

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

总结

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...