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

laiyouming · 2025-03-27 09:37:30 · 题解

思路

我们先和并区间(就是将 [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。

代码

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