Codeforces C.Elections(三分+暴力)

53 阅读 0 评论 35 点赞

我是靠谱客的博主平淡篮球，最近开发中收集的这篇文章主要介绍Codeforces C.Elections(三分+暴力)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接:

Problem - 457C - Codeforces

题意:

给定n个选民，此后n行，每行给一个整数a和b，a为选民原本打算投给的候选人的编号，b为收买该选民需要的花费。0号候选人为你自己，花费也是0。

票数最多的候选人会获胜(严格大于其他候选人的票数)，你想要让自己获胜，你需要买通其他投票人，使得他们投给0号票。问最少可以多少花多少钱，使得0号获胜。

样例:

输入样例1

输出样例1

输入样例2

输出样例2

思路:

题目要求我们找一个最小花费，使我(0号候选人)的得票数严格大于其他人的，一开始想如何排序然后贪心的去选，但发现情况实在忒多了，不能得到一个贪心策略，就是说按这个顺序收买能使我(0号)获胜而且花费最少。

我们可以从要收买的票数去考虑，如果说我要收买的票数确定了，那么对应这个票数下的最小花费我可以去贪心的确定。

首先我要收买的票数确定了，那我的总票数也就确定了(总票数=原来选我的+我收买的)，然后我必须要做的就是要将其他候选人的得票数控制在总票数-1 之下。超过了，我就按花费从小到大将的投他们的候选人收买掉。

如果说做完这一步发现我要收买的人的数量超过了我最开始确定的要收买的票数，说明我假设的这个票数不行，那这个花费就可以看作是无穷大。如果正好相等，则这个花费就是收买这些人的花费，如果小于我最开始确定的要收买的票数，那么我就从剩余的还未收买的人里面继续按花费由小到大收买，直至等于我最开始确定的要收买的票数。

可以发现，随票数的增长，花费是一个凹函数。

最开始收买的人太少（mid=0），无法达到要求，花费为无穷大，直到某个票数（mid=1，收买1，花费5），达到获胜要求了，但不一定是最优。

达到最优解后（mid=2,收买2，3，花费为2），再往后我拉的选票越多，花费越多。

代码:

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9+10;
const int N=1e5+10;
int n;
vector<int> vc[N];
int zn=0,m=0,cnt=0;
int _plus[N];//用于保存剩余还未收买的人 
int check(int mid){
	if(mid>cnt)
		return inf;
	//0买mid票，加上自己有的zn票，现有x票 
	int x=mid+zn;
	int sum=0,pay=0;//需要购买的票数及花费 
	for(int i=1;i<=m;i++){
		int sz=vc[i].size()-x;
		// 
		for(int j=0;j<=sz;j++){
			sum++;
			pay+=vc[i][j];
		}
	}
	if(sum>mid)
		return inf;
	else if(sum==mid)
		return pay;
	else{
		//还差mid-sum票没有买 
		int tt=0;
		for(int i=1;i<=m;i++){
			int pp=vc[i].size()-x+1;
			for(int j=max(0,pp);j<vc[i].size();j++){//i有w票，要让他减少到x-1票
				_plus[++tt]=vc[i][j];
			}
		}
		sort(_plus+1,_plus+tt+1);
		//从剩余还未收买的人里选择mid-sum个花费最少的 
		for(int i=1;i<=mid-sum;i++){
			pay+=_plus[i];
		}
		return pay;
	}
}
int tri_search(int l,int r){
	// 求凹函数的极小值
	int f1,f2;
	while(l < r) {
	    int lp = l + (r - l) / 3;
	    int rp = r - (r - l) / 3;
	    f1 = check(lp),f2 = check(rp);
	    if(f1 <= f2) 
			r = rp - 1;
	    else 
			l = lp + 1;
	}
	//查找的是极小值
	return min(f1,f2);
	//查找的是极小值对应的下标
	return f1<f2?l:r;
} 
int main(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a,&b);
		if(b==0)
			zn++;
		else{
			vc[a].push_back(b);
			cnt++;//选民投给其他人的票数 
			if(a>m)
				m=a;//出现的最大的选民编号 
		}
	}	
	int ma=0;
	for(int i=1;i<=m;i++){
		sort(vc[i].begin(),vc[i].end());
		if(ma<vc[i].size()){
			ma=vc[i].size();
		}
	}
	if(zn>ma){
		printf("0");
		return 0;
	}
	int l=0,r=cnt+1;
	printf("%d",tri_search(l,r));
}