Closest Cow Wins

题意

数轴上有若干块草地，每块草地有位置和美味值。Nhoj 已经放了一些牛，John 还能放 $N$ 头牛。

一块草地归离它最近的牛所属的农夫；如果 John 和 Nhoj 的牛距离相同，则归 Nhoj。

要求 John 最多能获得多少美味值。

思路

先看一个小数据暴力。它枚举一些可能改变覆盖关系的位置，用 bitmask DP 判断最多能覆盖哪些草地。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118/**
 * 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 19:35
 * update_at: 2026-07-11 19:38
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXK = 16;

int k, m, n;
ll patch_x[MAXK], patch_t[MAXK];
ll enemy_x[MAXK];
ll candidate_x2[500];
int candidate_cnt;
bool reach[20][1 << MAXK];

bool is_enemy_position(ll x2) {
    for (int i = 1; i <= m; i++) {
        if (x2 == 2 * enemy_x[i]) {
            return true;
        }
    }
    return false;
}

ll nearest_enemy_dist2(int id) {
    ll best = (1LL << 60);
    for (int i = 1; i <= m; i++) {
        ll d = llabs(patch_x[id] - enemy_x[i]) * 2;
        if (best > d) best = d;
    }
    return best;
}

void add_candidate(ll x2) {
    if (is_enemy_position(x2)) return;
    for (int i = 0; i < candidate_cnt; i++) {
        if (candidate_x2[i] == x2) return;
    }
    candidate_x2[candidate_cnt++] = x2;
}

int cover_mask(ll x2) {
    int mask = 0;
    for (int i = 1; i <= k; i++) {
        ll d_john = llabs(x2 - 2 * patch_x[i]);
        ll d_enemy = nearest_enemy_dist2(i);
        if (d_john < d_enemy) {
            mask |= 1 << (i - 1);
        }
    }
    return mask;
}

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

    cin >> k >> m >> n;
    for (int i = 1; i <= k; i++) {
        cin >> patch_x[i] >> patch_t[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> enemy_x[i];
    }

    vector<ll> endpoints;
    for (int i = 1; i <= k; i++) {
        ll best = nearest_enemy_dist2(i) / 2;
        endpoints.push_back(patch_x[i] - best);
        endpoints.push_back(patch_x[i] + best);
        add_candidate(2 * patch_x[i]);
    }

    sort(endpoints.begin(), endpoints.end());
    endpoints.erase(unique(endpoints.begin(), endpoints.end()), endpoints.end());
    for (int i = 0; i + 1 < (int)endpoints.size(); i++) {
        if (endpoints[i] < endpoints[i + 1]) {
            add_candidate(endpoints[i] + endpoints[i + 1]);
        }
    }

    int full = 1 << k;
    reach[0][0] = true;
    for (int used = 0; used < n; used++) {
        for (int mask = 0; mask < full; mask++) {
            if (!reach[used][mask]) continue;
            for (int i = 0; i < candidate_cnt; i++) {
                int nxt = mask | cover_mask(candidate_x2[i]);
                reach[used + 1][nxt] = true;
            }
        }
    }

    ll ans = 0;
    for (int used = 0; used <= n; used++) {
        for (int mask = 0; mask < full; mask++) {
            if (!reach[used][mask]) continue;
            ll sum = 0;
            for (int i = 1; i <= k; i++) {
                if (mask & (1 << (i - 1))) {
                    sum += patch_t[i];
                }
            }
            if (ans < sum) ans = sum;
        }
    }

    cout << ans << '\n';

    return 0;
}

满分做法从 Nhoj 的牛入手。Nhoj 的牛把数轴切成若干区间，每个区间可以独立考虑。

最左边和最右边的区间只有一侧有 Nhoj 的牛，所以 John 只要放一头牛，就能拿走这个区间内所有草地。

中间区间比较关键。设两端 Nhoj 的牛位置是 L 和 R，区间宽度是：

text

1width = R - L

如果 John 在这个区间里放一头牛，那么她能拿到的草地位置会形成一个连续窗口，而且这个窗口长度必须严格小于 $width / 2$ 。严格小于是因为距离相等时 Nhoj 获胜。

所以对于每个中间区间：

two：两头 John 的牛可以拿走区间内所有草地美味值；
one：一头 John 的牛能拿到的最大窗口和，用双指针滑动计算。

样例里区间 (7,11) 中有草地 8,10，美味值分别是 10,8。一头牛最多只能覆盖其中一段窗口；而两头牛可以分别贴近两侧，把整个区间内的草地都拿走。

最后怎么合并所有区间？对每个区间加入两个候选增益：

text

1
2第一头牛增益 = one
第二头牛增益 = two - one

边界区间只有一个候选增益，也就是整个区间总和。

把所有候选增益从大到小排序，取前 $N$ 个相加即可。这个贪心成立的关键是：对同一个区间，第二头牛的额外收益不会超过第一头牛的收益，也就是：

text

1two - one <= one

因此排序取前缀时，如果选到了某个区间的第二头牛收益，一定也会先选到它的第一头牛收益。

代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * 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 19:35
 * update_at: 2026-07-11 19:38
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Item {
    ll x;
    ll t;
    int is_cow; // 1 表示 Nhoj 的牛，0 表示草地
};

int k, m, n;
vector<Item> a;
vector<ll> gain;

bool cmp_item(Item p, Item q) {
    return p.x < q.x;
}

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

    cin >> k >> m >> n;
    for (int i = 1; i <= k; i++) {
        ll p, t;
        cin >> p >> t;
        a.push_back((Item){p, t, 0});
    }
    for (int i = 1; i <= m; i++) {
        ll f;
        cin >> f;
        a.push_back((Item){f, 0, 1});
    }

    sort(a.begin(), a.end(), cmp_item);

    int last_cow = -1;
    ll segment_sum = 0;

    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i].is_cow == 0) {
            segment_sum += a[i].t;
            continue;
        }

        if (last_cow == -1) {
            // 最左边没有 Nhoj 的牛，一头 John 的牛可以全拿。
            gain.push_back(segment_sum);
        } else {
            ll best_one = 0;
            ll cur_sum = 0;
            int r = last_cow;
            ll width = a[i].x - a[last_cow].x;

            // 中间区间：一头牛能覆盖一个长度小于 width/2 的窗口。
            for (int l = last_cow + 1; l < i; l++) {
                while (r + 1 < i && (a[r + 1].x - a[l].x) * 2 < width) {
                    r++;
                    cur_sum += a[r].t;
                }
                if (best_one < cur_sum) {
                    best_one = cur_sum;
                }
                cur_sum -= a[l].t;
            }

            gain.push_back(best_one);
            gain.push_back(segment_sum - best_one);
        }

        last_cow = i;
        segment_sum = 0;
    }

    // 最右边没有 Nhoj 的牛，也可以用一头牛全拿。
    gain.push_back(segment_sum);

    sort(gain.begin(), gain.end(), greater<ll>());

    ll ans = 0;
    for (int i = 0; i < n && i < (int)gain.size(); i++) {
        ans += gain[i];
    }

    cout << ans << '\n';

    return 0;
}

复杂度

排序所有草地和 Nhoj 的牛需要 $O((K+M)\log(K+M))$ 。

每个草地在双指针过程中进入和离开窗口常数次，区间处理总计 $O(K+M)$ 。

最后排序候选增益，复杂度 $O(M\log M)$ 。

总时间复杂度为 $O((K+M)\log(K+M))$ ，空间复杂度为 $O(K+M)$ 。

总结

本题的关键是把数轴按 Nhoj 的牛切开。

每个中间区间最多需要两头 John 的牛，一头牛的最优贡献是固定长度窗口最大和；把第一头和第二头的增益拆开放进候选列表，就能用排序贪心完成全局选择。

目录

题意

思路

代码

复杂度

总结