# 我没有说谎 ## 题目描述 小明参加了一场大型的 "欺诈游戏"，现在已经来到了最后一轮环节，最后一个环节还剩下 $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)，在给定的数据范围内是有效的。

相关问题

以下四个嫌疑人的辩词，三个人中只有一个人撒谎，请找出凶手A：不是我 B：是C C：是D D：C在说谎 用C语言表示该算法

#include <stdio.h>

int main() {
    int a = 0, b = 0, c = 0, d = 0;
    a = !(b || c || d); // A说不是他
    b = c; // B说是C
    c = d; // C说是D
    d = !c; // D说C在说谎

    if (a + b + c + d == 1) { // 只有一个人说谎
        if (a) {
            printf("A is the killer.");
        } else if (b) {
            printf("B is the killer.");
        } else if (c) {
            printf("C is the killer.");
        } else {
            printf("D is the killer.");
        }
    } else {
        printf("Cannot determine the killer.");
    }

    return 0;
}

以下四个嫌疑人的辩词，三个人中只有一个人撒谎，请找出凶手A：不是我 B：是C C：是D D：C在说谎，请你用GO语言表示出来

package main

import "fmt"

func main() {
    a := false
    b := false
    c := false
    d := false

    if !a && b && c || d && !c {
        fmt.Println("A是凶手")
    } else {
        fmt.Println("A不是凶手")
    }
}