2298: [HAOI2011]problem a
?id=2298 Time Limit: 10 Sec Memory Limit: 256 MB Submit: 696 Solved: 307 [Submit][Status][Discuss] 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
思路：其实我们可以很巧妙的把这道题转化成一道线段覆盖的问题，怎么转化呢？ 对于每一个描述，，我们可以根据他所描述的比他高的和比他矮的人数来构造一条线段，左端点l即为y+1，右端点r为n-x。 当我们转化成线段以后，这一段线段就表示着分数相同的人数，那么显然，只有与这个线段完全重合的线段是符合要求的，对于有交集的线段一定是有一个说谎的，但是对于完全重合的线段，还是有可能出现说谎的情况，因为，当完全重合的线段的数量大于这个线段的长度时，就有num-len个人说谎。 这样我们就可以把这个问题转化成一个线段覆盖的问题了，我们只需要求出有多少重合的线段，那么这个线段的权值就是这个数。然后我们再做带权值的线段覆盖就好了。 至于怎么在O（n+n*log(n)）的时间内做出来呢：先按照右端点排序，然后从前向后枚举每一个线段，用f数组记录在当前坐标时能取到的最大值：f[a[i].r]=f[a[i].l-1]+a[i].v; 至于为什么是f[a[i].l-1]呢？因为由于这个问题的特殊性，可能会出现【x，x】这种线段，所以为了避免比较麻烦的问题，就这样处理了。再做的时候还需要一直维护着f数组，我们用一个now变量，一直跟着右端点走，总共用（n）的时间来维护f数组。 最后还有一点，其实这个题可以不用map（因为我不会。。。）
;struct S{int l,r,v;}a[100010];int n,f[100010],m;inline int in(){char c=getchar();int x=0;while(c<‘0’||c>’9′)c=getchar();for(;c>=’0’&&c<=’9’;c=getchar())x=x*10+c-‘0’;return x;}bool cmp(S x,S y){if(x.r<y.r) return true;if(x.r==y.r&&x.l<y.l) return true;return false;}int main(){int i,j,x,y,ans=0,num,maxn=0,now=0,sum=0;n=in();m=n;for(i=1;i<=n;++i){x=in();y=in();if(x+y>=n) {ans+=1;continue;}a[i-ans].l=y+1;a[i-ans].r=n-x;}n-=ans;sort(a+1,a+n+1,cmp);for(i=1;i<=n;++i){num=1;while(1){if(a[i+1].l==a[i].l&&a[i+1].r==a[i].r){num+=1;i+=1;sum+=1;}else break;}a[i].v=min(num,a[i].r-a[i].l+1);f[a[i].r]=f[a[i].l-1]+a[i].v;while(1){maxn=maxn>f[now]?maxn:f[now];f[now]=maxn;now+=1;if(now==a[i].r+1){now-=1;break;}}if(i!=n&&a[i].r<a[i+1].l){while(1){f[now]=maxn;now+=1;if(now==a[i+1].l+1){now-=1;break;}}}}cout<<m-maxn<<endl;}
朋友，旭日正在升起，每一份付出，
