BZOJ_2298_[HAOI2011]problem a

BZOJ_2298_[HAOI2011]problem a_线段树

Description

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

Input

第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi

Output

一个整数，表示最少有几个人说谎

Sample Input

2 0

0 2

2 2

Sample Output

HINT

100%的数据满足： 1≤n≤100000 0≤ai、bi≤n

分析：

首先对于每个人的说法ai,bi，可以把它转换一下，变成从ai+1~n-bi这段区间人的成绩都是相等的。

非常像贪心对吧，http://www.cnblogs.com/suika/p/8711400.html

但需要注意的是，这里每个人的ai,bi可能是相等的，这时他们说的一定同时对或同时错，和上面那道题不同，我们不知道这段区间剩余空间是多少。

于是我们将ai,bi相等的人合并，这样贪心就不能做了。

先排序再DP，设f[i]为从1~i这段区间最多能符合多少人的说法，对于每个说法ai,bi,用1~ai-1中的最大值+1来更新f[bi]。

注意ai,bi相等的人合并时个数要和区间长度取较小值。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100050

#define ls p<<1

#define rs p<<1|1

int t[N<<2],del[N<<2],n;

struct A {

    int l,r,cnt;

}a[N],v[N];

bool cmp(const A &x,const A &y){

    if(x.r==y.r) return x.l>y.l;

    return x.r<y.r;

}

/*void build(int l,int r,int p) {

    if(l==r) {

        t[p]=1; return ;

    }

    int mid=l+r>>1;

    build(l,mid,ls);

    build(mid+1,r,rs);

    t[p]=1;

}*/

void update(int l,int r,int x,int y,int p) {

    if(l==r) {

        t[p]=max(t[p],y); return ;

    }

    int mid=l+r>>1;

    if(x<=mid) update(l,mid,x,y,ls);

    else update(mid+1,r,x,y,rs);

    t[p]=max(t[ls],t[rs]);

}

int query(int l,int r,int x,int y,int p) {

    if(x<=l&&y>=r) return t[p];

    int mid=l+r>>1,re=0;

    if(x<=mid) re=max(re,query(l,mid,x,y,ls));

    if(y>mid) re=max(re,query(mid+1,r,x,y,rs));

    return re;

}

int main() {

    scanf("%d",&n);

    int i,x,y,tot=0,ans=0;

    for(i=1;i<=n;i++) {

        scanf("%d%d",&x,&y);

        swap(x,y);

        a[i].l=x+1; a[i].r=n-y;

    }

    sort(a+1,a+n+1,cmp);a[0].l=645656;

    for(i=1;i<=n;i++) {

        if(a[i].l!=a[i-1].l||a[i].r!=a[i-1].r) v[++tot].l=a[i].l,v[tot].r=a[i].r;

        v[tot].cnt++;

    }

    /*build(1,n,1);

    for(i=1;i<=tot;i++) {

        if(v[i].l>v[i].r||v[i].l<1||v[i].r>n) continue;

        int tmp=query(1,n,v[i].l,v[i].r,1);

        if(tmp>0) {

            ans+=min(v[i].cnt,v[i].r-v[i].l+1);

            update(1,n,v[i].l,v[i].r,1);

        }

    }*/

    for(i=1;i<=tot;i++) {

        if(v[i].l>v[i].r||v[i].l<1||v[i].r>n) continue;

        int tmp=query(0,n,0,v[i].l-1,1)+min(v[i].cnt,v[i].r-v[i].l+1);

        ans=max(ans,tmp);

        update(0,n,v[i].r,tmp,1);

    }

    printf("%d\n",n-ans);

}

巴特西