题解：P2519 [HAOI2011] problem a

· · 题解

题解：P2519 [HAOI2011] problem a

喜提最劣解

思路

题目中说到第 i 个人有 a_i 个人成绩更低，b_i 个人成绩更高，我们设 l_i=a_i+1,r_i=n-b_i，那么这个人在按成绩排序后所在的可能区间即为 [l_i,r_i]，当然 l_i>r_i 的情况显然是不合法的。

我们可以用类似差分约束的方法做，对于每一个区间 [l_i,r_i]，将他视为 [l_i,r_i+1)（方便转移），然后在点 l_i 与点 r_i+1 之间建一条边，长度为在这个区间的人的数量和区间长度的最小值，最后从点 0 开始跑最长路即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,dp[100010],mx[100010];
struct N{
    int a,b;
}a[100010];
bool cmp(N a,N b){
    if(a.a!=b.a)return a.a<b.a;
    return a.b<b.b;
}
int m;
struct P{
    int l,r,k;
}c[100010];
bool Cmp(P a,P b){
    if(a.r!=b.r)return a.r<b.r;
    return a.l<b.l;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        int l=a[i].a+1,r=n-a[i].b;
        a[i].a=l;a[i].b=r;
    }
    sort(a+1,a+1+n,cmp);
    P pa={-1,-1,1};
    for(int i=1;i<=n;i++){
        if(a[i].a>a[i].b)continue;
        if(pa.l==-1||pa.l!=a[i].a||pa.r!=a[i].b){
            if(pa.l!=-1)c[++m]=pa;
            pa={a[i].a,a[i].b,1};
        }
        else pa.k++;
    }
    if(pa.l!=-1)c[++m]=pa;
    sort(c+1,c+1+m,Cmp);
    for(int i=1;i<=m;i++){
        int l=1,r=i-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(c[mid].r>=c[i].l)r=mid-1;
            else l=mid;
        }
        dp[i]=max(dp[i-1],dp[l]+min(c[i].r-c[i].l+1,c[i].k));
    }
    cout<<n-dp[m];
    return 0;
}