题目传送门：Problem - 1020C - Codeforces
这是一道不错的思维题，也是贪心题，可用三分，也可以不用。
题目大意
选举在即，有N个人，M个党派。但是可以花钱让某个人改变投票，自己的党派为1，最少花多少钱可以使自己赢得选举（1的票数分别严格大于所有其他党派的票数）？
思路
这道题一拿到手没什么思路啊，感觉是Greedy（贪心），但是又想不出什么好策略，没办法从局部最优推向全局最优。
看了一眼数据范围，尼玛，才3000，直接一手暴力。复杂度O(N ^ 2)，嗯可以。
思路就是枚举一个k表示阈值，使得1的票数大于等于k，所有其他党派票数都严格小于k，由此计算一个cost，再取最小cost即可。
计算cost的方法是：将人们的投票情况根据价格排序，然后从小到大枚举，如果当前这个人投的党派不是党派1且票数大于等于k，那么这个人的想法就应该改变，就收买他，并给他打上标记。最后再遍历一遍，确保1的票数大于等于k，注意打上标记的表示这个人已经收买，不能再收买。最后将收买所需价格返回即可。
交了一发，耗时60ms，还行。
你以为这样就结束了？在枚举的过程中发现，这个cost具有单调性，随k增大，先减后增，所以可以用三分求到最小值。于是乎，将原本的遍历k改成三分就行了。复杂度O(N * logN)，耗时15ms。
代码
/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <bitset>
#include <cstring>
#include <algorithm>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
const int maxn = 3009,inf = 1e12;
int N, M;
int vote[maxn];
PII peo[maxn];//people表示人们的票{被选举人， 价格}
bool cmp(PII a,PII b){return a.se < b.se;}
int cost(int k)
{
int v[maxn];memcpy(v, vote, sizeof vote);
bitset<maxn> vis;//表示是否买过
int res = 0;//收买人心的总价格
for(int i = 1;i <= N; ++ i)
{
int x = peo[i].fi, y = peo[i].se;
if(x != 1 && v[x] >= k)res += y, v[x] --, v[1] ++, vis[i] = 1;
}
for(int i = 1;i <= N && v[1] < k; ++ i)//如果v[1]不够 k 个
{
int x = peo[i].fi, y = peo[i].se;
if(x != 1 && !vis[i])res += y, v[x] --, v[1] ++;
}
return res;
}
signed main()
{
cin >> N >> M;//N为人数，M为党派数量
for(int i = 1;i <= N; ++ i)
{
int x, y;cin >> x >> y;
vote[x] ++;
peo[i] = {x, y};
}
sort(peo + 1, peo + 1 + N, cmp);//将人们的票排序
int l = 0, r = N;
while(l + 1 != r)
{
int mid = (l + r) / 2;
int midmid = (mid + r) / 2;
if(cost(mid) < cost(midmid))r = midmid;
else l = mid;
}
cout << min(cost(l),cost(r)) << '\n';
return 0;
}
文章评论