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

思路

我们先和并区间(就是将

[l_i,r_i]

和

[r_i+1,r_j]

合并成

[l_i,r_j]

)，然后就看每一个区间的两端(对于所有区间

[l_i,r_i]

我们看

|(l_i-1)-s|

和

|(r_i+1)-s|

的

min

)，最后记录答案。

注意：要注意建筑编号为

1\sim n

，

l_i-1

可能小于1，

r_i+1

可能大于

n

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,ans=1e18,ans2,top;
pair<long long,long long>a[1001];
int main(){
	scanf("%lld%lld%lld",&n,&m,&t);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&a[i].first,&a[i].second);
	}
	sort(a+1,a+m+1);
	top=0;
	for(int i=1;i<=m;i++){
		if(i==1||a[i].first!=a[top].second+1){
			a[++top]=a[i];
		}
		else{
			a[top].second=a[i].second;
		}
	}
	for(int i=1;i<=top;i++){
		long long x=a[i].first,y=a[i].second;
		x--,y++;
		if(x>=1&&abs(x-t)<ans){
			ans=abs(x-t),ans2=x;
		}
		if(y<=n&&abs(y-t)<ans){
			ans=abs(y-t),ans2=y;
		}
		if(x>=1&&abs(x-t)==ans){
			ans2=min(ans2,x);
		}
		if(y<=n&&abs(y-t)==ans){
			ans2=min(ans2,y);
		}
	}
	printf("%lld",ans2);
}

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

文章操作

思路

代码

相关推荐

评论

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