|
题目链接：https://codeforces.com/contest/1020/problem/C
题意是有n个政客，m个政党，每个政客都有一个支持的政党，现在想要让1政党成功选举，那么它的条件就是它的票数要大于其他的任意一个政党，现在可以去贿赂政客使他去投1号政党，问最小花费。
一道巧妙的思维题，思路就是枚举1号政党的最终票数，如果有的政党的票数大于1号的票数，就把它买至小于当前枚举的票数就好了，如果最终还是不够当前枚举的票数，那么就从最便宜的政客开始买，直至买够枚举的票数，在这个过程中更新花费的最小值。直接看代码吧
AC代码：
#include <bits/stdc++.h>
#define maxn 3005
#define ll long long
using namespace std;
struct Node{
int x,y;
}Edge[maxn];
int pre[maxn];
int n,m;
bool cmp(Node a, Node b){
return a.y < b.y;
}
int main()
{
map<int,int> ma;
scanf("%d%d",&n,&m);
int cnt = 0;
for(int i=0;i<n;i++){
scanf("%d%d",&Edge[i].x, &Edge[i].y);
ma[Edge[i].x] ++;
}
ll ans = 0x3f3f3f3f3f3f3f3f;
sort(Edge , Edge + n, cmp);
for(int i=ma[1];i<=n;i++){
memset(pre, 0, sizeof(pre)); // 用来记录第j个政党比i多的票数
int cnt = 0;
ll sum = 0;
for(int j=2;j<=m;j++){ // 遍历查找大于等于i的政党
if(ma[j] >= i){
pre[j] = ma[j] - i + 1;
cnt += pre[j];
}
}
int xx = i - ma[1];
if(xx < cnt) continue; // 不可行的情况
xx -= cnt;
for(int j=0;j<n;j++){
if(pre[Edge[j].x]){
sum += Edge[j].y;
pre[Edge[j].x] --;
}
else{
if(xx != 0 && Edge[j].x != 1) sum += Edge[j].y, xx --;
}
}
ans = min(ans, sum);
}
printf("%lld\n", ans);
return 0;
}
| 
转播
