Counting Liars
Counting Liars
题目链接（USACO 2022 US Open Contest, Bronze Problem 2）
题目描述
农夫约翰有 N 头奶牛（不包括 Bessie）。每头牛给出一条关于
Bessie 躲藏位置的陈述：
- 若某头牛说
L p：表示 Bessie 的位置 ≤ p； - 若某头牛说
G p：表示 Bessie 的位置 ≥ p。
可能并非所有牛都说了真话，你需要找出至少要让多少头牛说谎，才能使得剩下的陈述存在某个位置
x 同时满足。
输出最少必须说谎的牛数。
数据范围：
1 <= N <= 10000 <= p <= 10^9
示例
示例 1
输入：
2
G 3
L 5解释： - Cow1：Bessie ≥ 3 - Cow2：Bessie ≤ 5
显然 3 ≤ Bessie ≤ 5 有解，所以 0
头说谎。
输出：
0示例 2
输入：
2
G 3
L 2解释： - Bessie ≥ 3 - Bessie ≤ 2
没有位置能同时满足，必须至少删除一条陈述 → 答案是 1。
输出：
1核心思路
假设 Bessie 位于位置 x，判断每条陈述真假：
L p为真 ⟺x ≤ p，为假 ⟺x > p；G p为真 ⟺x ≥ p，为假 ⟺x < p。
关键观察：把所有 p 排序后，最优的
x 一定可以取某个 p_i（或位于两个
p 之间，效果等价）。因此只需枚举每个 p_i
作为分界点。
固定分界点为 x = cow[i].first（排序后第 i
头牛的 p），则：
- 左侧的
L说谎：p < x的L陈述为假（因为x > p）； - 右侧的
G说谎：p > x的G陈述为假（因为x < p）。
说谎总数 = left_lying[i] + right_lying[i]，其中：
left_lying[i]：排序后前i个元素中L的数量；right_lying[i]：排序后第i+1到末尾中G的数量。
枚举所有分界点，取最小值即可。
为什么只用枚举
p_i：说谎数随x变化，只在跨越某个p_i时改变。因此每一段区间内说谎数恒定，取任意端点都行。
方法：排序 + 前缀和
思路及解法
- 把每头牛的
(p, 类型)存入数组，按p升序排序； - 预处理
left_lying[i]：排序后前i个元素中L的数量（不含第i个）； - 预处理
right_lying[i]：排序后第i+1个到末尾中G的数量（不含第i个）； - 枚举每个
i，计算left_lying[i] + right_lying[i]，取最小值。
为什么只统计严格左侧的 L 和严格右侧的
G：
- 对于
x = cow[i].first：- 位于
x左侧的L p（p < x）一定为假； - 位于
x右侧的G p（p > x）一定为假； - 位于
x本身或另一侧的陈述都能被x满足（或至少不冲突）。
- 位于
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, char>> cow(n);
for (int i = 0; i < n; i++) {
cin >> cow[i].second >> cow[i].first;
}
sort(cow.begin(), cow.end());
// left_lying[i]：前 i 个元素中 L 的数量（不含 cow[i]）
vector<int> left_lying(n);
for (int i = 1; i < n; i++) {
left_lying[i] = left_lying[i - 1];
if (cow[i - 1].second == 'L') {
left_lying[i]++;
}
}
// right_lying[i]：第 i+1 个到末尾中 G 的数量（不含 cow[i]）
vector<int> right_lying(n);
for (int i = n - 2; i >= 0; i--) {
right_lying[i] = right_lying[i + 1];
if (cow[i + 1].second == 'G') {
right_lying[i]++;
}
}
int ans = n;
for (int i = 0; i < n; i++) {
ans = min(ans, left_lying[i] + right_lying[i]);
}
cout << ans;
return 0;
}Python 版本
def solve():
n = int(input())
cows = []
for _ in range(n):
typ, p = input().split()
cows.append((int(p), typ))
cows.sort()
left_lying = [0] * n
for i in range(1, n):
left_lying[i] = left_lying[i - 1]
if cows[i - 1][1] == 'L':
left_lying[i] += 1
right_lying = [0] * n
for i in range(n - 2, -1, -1):
right_lying[i] = right_lying[i + 1]
if cows[i + 1][1] == 'G':
right_lying[i] += 1
ans = n
for i in range(n):
ans = min(ans, left_lying[i] + right_lying[i])
print(ans)
if __name__ == "__main__":
solve()复杂度分析
- 时间复杂度：，排序开销，剩余部分 。
- 空间复杂度：，存储数组和前缀。
关键细节
1. 为什么枚举 p_i
就够了
说谎数 left_lying(x) + right_lying(x) 在 x
从一个 p_i 移动到下一个 p_{i+1}
之间是常数：
- 左侧的
L数量不变（没有新的L跨过x）； - 右侧的
G数量不变。
只有 x 恰好跨过某个 p_i
时，说谎数才可能变化。因此每段区间取一个代表点即可，p_i
是最方便的选择。
2. left_lying 和
right_lying 的边界
left_lying[0] = 0：第 0 头牛左侧没有元素；right_lying[n-1] = 0：最后一头牛右侧没有元素；- 当
n = 1时，left_lying[0] + right_lying[0] = 0，答案 0（只有一头牛，取x = p_0即可满足）。
3. 为什么只统计「严格左侧的 L」和「严格右侧的 G」
考虑 x = cow[i].first：
- 对于
L p，若p < x，则x > p，陈述「位置 ≤ p」为假 → 说谎； - 对于
L p，若p >= x，则x <= p，陈述为真 → 不算说谎； - 对于
G p，若p > x，则x < p，陈述「位置 ≥ p」为假 → 说谎； - 对于
G p，若p <= x，则x >= p，陈述为真 → 不算说谎。
所以只有「严格左侧的 L」和「严格右侧的
G」需要被计入说谎，与代码逻辑一致。
4. 相同 p 的处理
若多个牛的 p 相同，排序后它们相邻。枚举到其中某一个作为
x 时，其他相同 p
的牛不会被计入「严格左侧」或「严格右侧」，所以不会重复统计，结果正确。
5. 文件输入输出
USACO 原题中一般从标准输入读取（本题 Bronze 官方未强制文件 IO），提交时按平台要求即可。若需要文件 IO：
freopen("liars.in", "r", stdin);
freopen("liars.out", "w", stdout);总结
- 本质：求一个位置
x，使「p < x的L」+「p > x的G」最少； - 关键观察：只需枚举某个
p_i作为分界点； - 做法：排序 + 前缀和（左侧
L计数、右侧G计数）； - 时间复杂度 ，空间复杂度 ；
- 通用套路：「选一个分界点使左右两边的谎言数之和最小」→ 排序 + 前缀和后缀统计。
相关题目
- USACO 2016 US Open Bronze. Diamond Collector（另一道 Bronze 枚举 + 排序题）
- USACO 2022 US Open Bronze Problem 1（同场 Bronze）
- LC 1356. 根据数字二进制下 1 的数目排序（排序 + 统计）
- LC 1450. 在既定时间做作业的学生人数（按时间点统计）