2298: [HAOI2011]problem a

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 1523  Solved: 756

[ ][ ][ ]

Description

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

 

Input

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

Output

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

 

Sample Input

3

2 0

0 2

2 2

Sample Output

1

HINT

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

 

题解：

　　这个题目还是比较巧妙的。

　　首先分析题意，一个人说出的其实是一个区间，表示ai+1~n-bi必须相等，并且其他位置都和这个区间的元素不相等，那么对于两个相交的区间，他们一定有一个是不合法的，对于相等的区间，假如说区间长度为len,那么区间个数超过len的显然超过的部分也是不和法，同理，相互包含的也是不合法的，所以每个区间，我们统计和他相等的区间个数作为权值，这样就转化为选择若干权值不想交的区间使得权值最大化。

　　分析到这，就是一个简单dp了，主要还是转化有一定的难度。

 

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define MAXN 100010using namespace std;struct node{ int l,r,maxx;}a[MAXN*4];struct qvjian{ int l,r,v;}qv[MAXN]; bool cmp(qvjian x,qvjian y){ if(x.l==y.l) return x.r
            
             mid) return query(xv*2+1,l,r); else return max(query(xv*2,l,mid),query(xv*2+1,mid+1,r));} void insert(int xv,int ps,int x){ int l=a[xv].l,r=a[xv].r,mid=(l+r)/2; if(l==r){ a[xv].maxx=max(a[xv].maxx,x); return; } if(ps<=mid) insert(xv*2,ps,x); else insert(xv*2+1,ps,x); pushup(xv);} int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int l,r;scanf("%d%d",&l,&r); l=l+1,r=n-r; if(l<=r) {qv[++num].l=l;qv[num].r=r,qv[num].v=1;} } sort(qv+1,qv+num+1,cmp); int ps=0; for(int i=1;i<=num;i++){ if(qv[ps].l==qv[i].l&&qv[ps].r==qv[i].r) qv[ps].v++; else qv[++ps]=qv[i]; } for(int i=1;i<=ps;i++){ int len=qv[i].r-qv[i].l+1; if(qv[i].v>len) qv[i].v=len; } build(1,1,n); int ans=0; for(int i=1;i<=n;i++){ int now; if(qv[i].l-1>0) now=qv[i].v+query(1,1,qv[i].l-1); else now=qv[i].v; ans=max(ans,now); insert(1,qv[i].r,now); } printf("%d\n",n-ans); return 0;}