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

SnowyIris · 2025-03-29 21:30:56 · 题解

传送门

第一眼看到这题可能会想直接 bool 数组暴力判断，但是看到 n 的范围自然会打消这个想法（虽然说实际数据好像没有到这个范围，暴力也能过 awa）。

但是我们可以看到，题目中 m 的范围极小，自然，我们要对不租赁的房子链的两端进行处理。

我们先找到学校 s 所在的区间内（由题目可知，必然有一段不租赁的房子链包含 s），那么我们让 r 为右侧最近端点，l 即为左侧最近端点，显然 l=r-1。

接下来，我们由 l 和 r 分别向两端搜索最近的可租赁的房子。

ps：每次增减 2 是为了保证 l 一直是左端点，r 同理。

ps2：由题目的数据保证可知，题目必然有解，所以当 l 搜到最左端并且等于 1 时，答案必然为 a_r+1，r 同理。

AC code

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