CF1020C
[TOC]
题意
这个题的背景是贿赂选民,从而让自己的组织能够上台.
自己组织的编号是1.
然后列出选民想要选的组织,以及收买他们的代价.
求最小代价.
输入
第一行给出n,m,表示选民数量和组织数量,组织按照[1,2,3…m]编号,范围都是[1,3000]
然后之后n行选民,每一行给出p,c,表示此位选民想投的组织和收买的代价 , 1<=p<m , 1<=c<=1e9
输出
输出最小代价
解析
这个题如果直接做,会发现不太好贪心,虽说是肯定优先选取代价最小的选民,但是如果目前只有一个组织在我党前面,那么或许收买她的选民比收买其他党的选民更划算(可见原题样例2),这样就造成了贪心的困难
我们再观察题目,发现n,m的范围都很小,不过3e3,所以我们可以考虑枚举我党想要到达的票数,我们假设票数是(k+1)(此处设计方便之后计算)然后我们朝着这个方向贪心,即对于其他党,如果票大于k,我们就按照代价递增的顺序收买其选民,使之票数等于k,我们将所有这种党处理过后,看票数是否到达了k+1,如果到达了,则处理结束,输出答案即可;如果尚未到达,则从所有选民中按照递增的顺序收买,收买过程中注意标记,避免同一个选民收买两次,当到达k+1时,输出答案
代码
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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#define ll long long
using namespace std;
bool vis[4000];
struct peo {
int id;
int cost;
peo(int id, int cost) : id(id), cost(cost) {}
};
bool cmp(peo &a, peo &b) {
return a.cost < b.cost;
}
int main() {
vector<peo> G[4000]; // 根据党派储存其选民
vector<peo> a; // 储存所有选民
int n, m;
cin >> n >> m;
ll sum = 0;
for (int i = 1; i <= n; ++i) {
int party, cost;
cin >> party >> cost;
if (party != 1) { // 不能收买自己的选民
a.push_back(peo(i, cost));
G[party].push_back(peo(i, cost));
} else {
++sum;
}
}
sort(a.begin(), a.end(), cmp);
for (int i = 1; i <= m; ++i) {
sort(G[i].begin(), G[i].end(), cmp);
}
ll mincost = static_cast<long long int>(1e18 + 7);
for (int k = 0; k < n; ++k) {
memset(vis, 0, sizeof(vis));
ll ans = 0;
int t = 0;
for (int i = 2; i <= m; ++i) {
int newTicket = 0;
while (G[i].size() - newTicket > k) { // 一直收买到只剩k个为止
ans += G[i][newTicket].cost;
vis[G[i][newTicket].id] = 1;
++newTicket;
}
t += newTicket;
}
int pos = 0;
while (t + sum <= k) { // 保证最后的选民是k+1
if (!vis[a[pos].id]) {
ans += a[pos].cost;
++t;
vis[a[pos].id] = 1;
}
++pos;
}
mincost = min(mincost, ans);
}
printf("%I64d\n", mincost);
return 0;
}
启示
类似之前的那个小丑和艺术家的题目(CF1138B),我感觉太过忽略了枚举在解数学题中的作用,尤其是在数据范围小的题目上更显得巧妙
