ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

【CodeForces】1020C. Elections(贪心 + 思维 + 三分)

2022年3月19日 558点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 三分 单调性 思维 贪心
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号