题目描述
一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)
输入格式
第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi
输出格式
一个整数，表示最少有几个人说谎
输入输出样例
输入 #1
3 2 0 0 2 2 2
输出 #1
1
说明/提示
100%的数据满足： 1≤n≤100000 0≤ai、bi≤n
思路：
转变题意：题目中的 ai bi 表示从1+ai 到 n-bi排名区间内的同学的分数相同，且与不属于该区间的同学分数一定不同。
考虑补集思想：最少说假话人数=总人数-最多说真话人数
而又显然：如果两个区间相交但不重合，则发生冲突。
比如一个人说第三名和第四名的成绩相同，另一个说第四名和第五名成绩相同，则必然有一个人说了假话
考虑给区间赋上权值：一个区间的权值=本质相同的区间总数，且最大为区间长度。
比如有五个人都说自己的排名是第三到第五名，则至多三个同学说真话。
于是题目就变成了一个区间覆盖问题qvq 求权值最大且互不相交的区间覆盖
DP即可。注意和【今年暑假不AC】不同，由于区间带权，不能直接贪心（爆零警告）
先以右端点为第一关键字，左端点为第二关键字排序。
定义DP [ i ] 表示右端点覆盖到 i 的合法方式最大权值。
dp[ r [ i ] ] = max (dp [ l [ i ] ] + w[ i ],dp [ r [ i ] ] ) ;
dp[ i ] = max ( dp [ i - 1 ] , dp [ i ] ) ;
值得一提的是第二个转移必须要在 i 之前的①转移都已完成（也即i<=当前右端点)。注意转移顺序，具体见代码（貌似又写丑了orz）
时间复杂度O（nlogn）
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; const int maxn=100005; int dp[maxn]; struct node{ int l,r,w; }a[maxn]; inline bool cmp(node a,node b) { if (a.r==b.r) return a.l<b.l; return a.r<b.r; } inline void init(int n) { int cnt_l=0,cnt_r=0,cnt_val=0; for (int i=1;i<=n;i++) { int now_l=a[i].l,now_r=a[i].r; if (now_l!=cnt_l || now_r!=cnt_r) { cnt_val=0; cnt_l=now_l,cnt_r=now_r; } cnt_val++; a[i].w=min(cnt_val,now_r-now_l+1); } } int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); a[i].l=x+1,a[i].r=n-y; } sort(a+1,a+n+1,cmp); init(n); int cnt=0; for (int i=1;i<=n;i++) { if (a[i].r<a[i].l) continue; if (a[i].r>cnt) { for (int j=cnt+1;j<=a[i].r;j++) dp[j]=max(dp[j],dp[j-1]); cnt=a[i].r; } int l=a[i].l,r=a[i].r; dp[r]=max(dp[r],dp[l-1]+a[i].w); } if (n>cnt) for (int i=cnt+1;i<=n;i++) dp[i]=max(dp[i],dp[i-1]); cout << n-dp[n]; }