专栏文章

题解：P11916 [PA 2025] 学区房 / Szkoła

SSnowyIris
P11916题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miprw3nm
此快照首次捕获于
2025/12/03 16:56
3 个月前
此快照最后确认于
2025/12/03 16:56
3 个月前
查看原文
传送门
第一眼看到这题可能会想直接 bool 数组暴力判断，但是看到 nn 的范围自然会打消这个想法（虽然说实际数据好像没有到这个范围，暴力也能过 awa）。
但是我们可以看到，题目中 mm 的范围极小，自然，我们要对不租赁的房子链的两端进行处理。
我们先找到学校 ss 所在的区间内（由题目可知，必然有一段不租赁的房子链包含 ss），那么我们让 rr 为右侧最近端点，ll 即为左侧最近端点，显然 l=r−1l=r-1。
接下来，我们由 ll 和 rr 分别向两端搜索最近的可租赁的房子。
ps：每次增减 22 是为了保证 ll 一直是左端点，rr 同理。
ps2：由题目的数据保证可知，题目必然有解，所以当 ll 搜到最左端并且等于 11 时，答案必然为 ar+1a_r+1，rr 同理。

AC code

CPP
#include<iostream>
#include<algorithm>
using namespace std;
#define f(n) for(int i=1;i<=n;i++)
#define ll long long
ll n,m,s,l,r; 
ll a[2025];
int main()
{
	cin>>n>>m>>s;
	f(m)cin>>a[i*2-2]>>a[i*2-1];//从0开始
	sort(a,a+2*m);
	while(a[r]<=s)
		if(a[r]==s&&r&1==1)break;//出现诸如(50,50)的情形时让r在右侧停下
		else r++;
	l=r-1;
	while(l>0&&a[l]-1==a[l-1])l-=2;
	while(r<=2*m-1&&a[r]+1==a[r+1])r+=2;
	if(a[l]<=1)cout<<a[r]+1;//左端没有房
	else if(a[r]==n)cout<<a[l]-1;//右端没有房
	else if(s-a[l]<=a[r]-s)cout<<a[l]-1;
	else cout<<a[r]+1;
	return 0;
}

评论

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

正在加载评论...