# 我没有说谎 ## 题目描述 小明参加了一场大型的 "欺诈游戏"，现在已经来到了最后一轮环节，最后一个环节还剩下 $n$ 个人，编号为 $1,2,\dots,n$。小明只要胜出，就能获得终极大奖 $1,000$ 万。 本轮游戏开始前，主办方会在大屏幕放映随机生成的 $n$ 个人的分数，也就是说大家都知道彼此的分数。在看完所有人的分数后，主办方要求每一个参与游戏的人，都说一句有几个人分数比我高，有几个人分数比我低，当然，这句话可以不是真实的，可以说谎。 每个人说完后，主办方收集了每一个人的回答，具体地，编号为 $i$ 的人说的是，"有 $a_i$ 个人分数比我高，有 $b_i$ 个人分数比我低"。 现在问，$n$ 个人中最少有几个人在说谎，如果小明回答对了这个问题，就可以获得大奖，请你帮帮小明。 ## 输入格式 输入第一行一个整数，表示参与最后一轮游戏的人数。 接下来 $n$ 行，每行两个正整数，第 $i+1$ 行为 $a_i$ 和 $b_i$ 含义与题目描述一致。 ## 输出格式 输出一行一个整数，表示在本轮游戏中，说谎人数的最少可能。 ## 样例 #1 ### 样例输入 #1 ``` 3 2 0 0 2 2 2 ``` ### 样例输出 #1 ``` 1 ``` ## 提示 【样例解释】 假设第 $1$ 句话是真话，因为有 $2$ 个人比他高，那么编号为 $1$ 分数排名第 $3$；同理，假设第 $2$ 句话是真话，$2$ 号排名第 $1$，确定了 $3$ 个人的排名为 $2,3,1$。 那么就是 $3$ 在说谎，说谎人数为 $1$ 人，并且可以通过枚举发现，说谎人数 $1$ 人就是最小值。 【数据范围】 对于 $20\%$ 的数据满足：$n\le 20$； 对于 $50\%$ 的数据满足：$n \le 1000$； 对于 $100\%$ 的数据满足： $1≤n≤10^5,0 \le a_i+b_i \le n$。

我们使用贪心算法来解决这个问题。
首，我们将所有人按照$a_i$的从大到小排序。然后，我们从往后遍历每个人，假设当前历到的人是第$i$个人。
在前面的$i-1$个人中，有$k$个人的$a$值于等于$i$，么这些人必在说谎，因为他们的分明显比第$i$人高。所以我们可以将说谎人数加上$k$。
然后，我们判断第$i$个人的$b_i$值是否小于等于$n-i$。如果小于等于，说明他在说谎，我们将说谎人数加。否则，他在说真话。
最后，说谎人数的最小可能就是我们得到的结果。
以下是使用Python实现的代码：
n = int(input())
people = []
for _ in range(n):
a, b = map(int, input().split())
people.append((a, b))

people.sort(reverse=True) # 按照a_i从大到小排序

lying_count = 0
for i in range(n):
k = sum(1 for j in range(i) if people[j][0] >= i) # 统计前面有多少个人的a值大于等于i
if k > people[i][1]: # 如果有k个人的a值大于等于i，但是b值小于k，说明第i个人在说谎
lying_count += 1

print(lying_count)
登录后复制
这个算法的时间复杂度为O(n^2)，在给定的数据范围内是有效的。