发现对于每个草地，假设距离和它最近的敌方牛距离为 d，那么想要拥有这块草地的话必须把点放在 (pi−d,pi+d) 这个开区间里。
下面是一个错误思路：
如果思考方向是往这些区间里放点，每次选择能给答案带来最大贡献的一段有效区间放一个点，是会挂掉的，因为可能不选最优的方法可以在更少点数把所有草场都选上，但是贪心的话可能选到了中间的区间导致无法覆盖所有的。
一个草场如果对应区间选了多次，也就只能算一次，这个方法的问题就在于可能忽略了这一点。但是样例是能过的。
我们考虑两个相邻敌方牛之间的所有草地，很容易发现我们最多放 2 个点就可以把这段区间里面所有的覆盖。
所以我们考虑如何往这几个敌方牛之间的区间放点最优，其实就是一个物品重量为 1 或 2 的背包问题，可以直接用一个堆贪心做。
放两个点是一定能得到区间内全部草场的，那么放一个点应该怎么统计呢？
我们可以每次固定放一个点能覆盖到的最靠左的草场，这个时候我们可以预处理出所有草场放点要求的左右边界，然后用双指针就能快速统计后面的哪些区间会和这段起点区间有交集啦，注意都是开区间，因为距离相同的草场可是属于对方的。由于在这两个敌方牛区间外的草场肯定存在敌方牛距离比在这个区间放点更近，所以我们每次只需要考虑两个敌方牛之间的草场就好。
（可以参考文章开头的一张图，对应了样例）
具体实现细节看代码。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int k, m, n;
cin >> k >> m >> n;
vector<pair<int, int>> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a.begin(), a.end(), [&](pair<int, int> x, pair<int, int> y) {
return x.first < y.first;
});
vector<int> f(m);
for (int i = 0; i < m; i++) {
cin >> f[i];
}
f.push_back(-1e9);
f.push_back(1e9 + 10);
sort(f.begin(), f.end());
priority_queue<int, vector<int>, greater<int>> pq;
int cntt = 0, ans = 0;
for (int i = 1; i < f.size(); i++) {
int p1 = lower_bound(a.begin(), a.end(), make_pair(f[i - 1], 114514)) - a.begin();
int p2 = upper_bound(a.begin(), a.end(), make_pair(f[i], 114514)) - a.begin();
int l = p1, r = p1 - 1, cnt1 = 0, cnt2 = 0, cnt = 0;
for (int j = p1; j < p2; j++) {
cnt2 += a[j].second;
int pos = a[l].first + min(f[i] - a[l].first, a[l].first - f[i - 1]);
while (r < p2 - 1 && pos > a[r + 1].first - min(f[i] - a[r + 1].first, a[r + 1].first - f[i - 1])) {
r++;
cnt += a[r].second;
}
cnt1 = max(cnt1, cnt);
cnt -= a[l].second;
l++;
}
cntt++;
pq.push(cnt1);
ans += cnt1;
cntt++;
pq.push(cnt2 - cnt1);
ans += cnt2 - cnt1;
while (cntt > n) {
cntt--;
ans -= pq.top();
pq.pop();
}
}
cout << ans;
return 0;
}
|
感觉写的好乱。。。
