Description:


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

 

Input:


第一行一个整数 \(n\) ,接下来 \(n\) 行每行两个整数,第 \(i+1\) 行的两个整数分别代表 \(a_i\)\(b_i\)

Output:


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

 

Sample Input:


Sample Output:


题解:


自己YY了一个算法 [摊手]

\(a_i\) 个人排在前 \(b_i\) 个人排在后,转变为排名区间 \([a_i+1, n-b_i]\) 分数相同。

答案就是n-最多的说真话人数。

然后题目变为选最多不重区间(完全相同的区间需要特判)。

把区间按照右端点第一关键字,左端点第二关键字排序, \(f[i]\) 表示选择第 \(i\) 个区间,前 \(i\) 个区间最多选择多少个。

可以得出状态转移 \(f_i = f_j + 1\) ,其中 \(j\) 的右端点小于 \(i\) 的左端点。

考虑用前缀和处理出 \(f_j\) 的最大值,在右端点集合中查询 \(i\) 的左端点,更新答案。

时间复杂度 \(O(nlog_2n)\)

代码如下: