Counting Liars

题意

Bessie 躲在数轴上的某个整数位置 h。

每头牛给出一条陈述：

G p：它说 $h >= p$ ；
L p：它说 $h <= p$ 。

要求选择一个位置 h，让撒谎的牛最少，输出最少数量。

思路

先看一个直接检查候选位置的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:27
 * update_at: 2026-07-11 17:28
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int INF = 1e9;

int n;
char type[MAXN];
long long p[MAXN];
long long candidate[MAXN * 3];
int candidate_cnt;

int count_liars(long long h) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (type[i] == 'G' && h < p[i]) {
            cnt++;
        }
        if (type[i] == 'L' && h > p[i]) {
            cnt++;
        }
    }
    return cnt;
}

void add_candidate(long long x) {
    candidate_cnt++;
    candidate[candidate_cnt] = x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> type[i] >> p[i];
        add_candidate(p[i]);
        if (p[i] > 0) {
            add_candidate(p[i] - 1);
        }
        add_candidate(p[i] + 1);
    }

    int ans = INF;
    for (int i = 1; i <= candidate_cnt; i++) {
        int liars = count_liars(candidate[i]);
        if (liars < ans) {
            ans = liars;
        }
    }

    cout << ans << '\n';

    return 0;
}

对于固定的藏身点 h，一条陈述是否为谎言很好判断：

G p 在 h < p 时是假话；
L p 在 h > p 时是假话。

关键问题是：不能枚举整个数轴，因为 $p_i$ 可以到 $10^9$ 。

官方解析的观察是，只需要枚举输入中出现过的坐标 p_i。

如果某个最优藏身点不等于任何 p_i，把它向左或向右移动到某个最近的 p_i，撒谎数量不会增加。因此一定存在一个最优位置正好等于某个 p_i。

于是做法很直接：

枚举 h = p[i]；
扫描所有陈述，统计与 h 不一致的数量；
对所有候选取最小值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:27
 * update_at: 2026-07-11 17:28
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int INF = 1e9;

int n;
char type[MAXN];
long long p[MAXN];

int count_liars(long long h) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (type[i] == 'G' && h < p[i]) {
            cnt++;
        }
        if (type[i] == 'L' && h > p[i]) {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> type[i] >> p[i];
    }

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        int liars = count_liars(p[i]);
        if (liars < ans) {
            ans = liars;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

枚举 N 个候选位置，每次扫描 N 条陈述。

时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$ 。

总结

本题的核心是缩小候选藏身点集合。

虽然数轴很大，但陈述真假只会在输入坐标附近发生变化，所以枚举所有 p_i 就足够得到最优答案。

目录

题意

思路

代码

复杂度

总结