P2519 [HAOI2011]problem a

方杰123 · 2022-10-14 10:41:36 · 个人记录

题目

思路

首先，我们可以算出每个人的排名的区间（因为有与他排名相同的人）。

那么合并排名相同的人后（最多不超过r-l+1个人，这里写错亲测70pts），这题就变成求最大权值不重合线段集。设f[i]表示选了i个线段的最大值。因为要满足r_{i-1}<l_i，所以把线段按照r_i排序，保证 r_{i-1}<l_i的线段全在i前面。f[i]=max(f[k])(r_k<l_i)，按照r_i为下标，树状数组优化即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
struct Su{
    int l,r,va;
    bool operator<(const Su t1)const{
        return r==t1.r?l<t1.l:r<t1.r;
    }
}S[N],C[N];
int n,tot,cnt,f[N],pre[N],maxn;
void add(int u,int x){
    for(int i=u;i<=n;i+=i&(-i))pre[i]=max(pre[i],x);
    return;
}
int query(int u){
    int res=0;
    for(int i=u;i>0;i-=i&(-i))res=max(res,pre[i]);return res;
}
int main(){int tl,tr;
    n=read();
    for(int i=1;i<=n;i++){
        tl=read()+1,tr=n-read();
        if(tl<=tr){S[++tot].l=tl,S[tot].r=tr,maxn=max(maxn,S[tot].r);}
    }
    sort(S+1,S+tot+1);
    for(int i=1;i<=tot;){
        int now=1;i++;
        while(S[i].l==S[i-1].l && S[i].r==S[i-1].r)now++,i++;
        C[++cnt].l=S[i-1].l,C[cnt].r=S[i-1].r,C[cnt].va=min(now,C[cnt].r-C[cnt].l+1);
    }
    for(int i=1;i<=cnt;i++){
        f[i]=query(C[i].l-1)+C[i].va;
        add(C[i].r,f[i]);
    }
    printf("%d",n-query(maxn));
    return 0;
}