Elections CodeForces - 1020C (贪心)

淩亂°似流年 2021-10-01 00:20 244阅读 0赞

大意: 有n个选民, m个党派, 第i个选民初始投$p\_i$一票, 可以花费$c\_i$改变投票, 求最少花费使得第一个党派的票数严格最大

假设最终第一个党派得票数$x$, 枚举$x$, 则对于所有票数$\\ge x$的党派, 贪心选择尽量小的c改选第一个党派.若最后票数还不够, 再从没改过的人中选择尽量小的改选即可

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    #define REP(i,a,n) for(int i=a;i<=n;++i)
    #define pb push_back
    #define x first
    #define y second
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N = 4e5+10, INF = 0x3f3f3f3f;
    int n, m;
    vector<pii> s[N];
    pii a[N];
    int vis[N];
    
    int main() {
    	scanf("%d%d", &n, &m);
    	REP(i,1,n) {
    		int x, y;
    		scanf("%d%d", &x, &y);
    		s[x].pb({y,i});
    		a[i] = {x==1?1e9:y,i};
    	}
    	sort(a+1, a+1+n);
    	REP(i,2,m) sort(s[i].begin(),s[i].end());
    	ll ans = 1e18;
    	REP(i,1,n) {
    		int tot = 0;
    		ll c = 0;
    		REP(j,2,m) if (s[j].size()>=i) {
    			for (int k=0; k<=s[j].size()-i; ++k) {
    				++tot, c+=s[j][k].x, vis[s[j][k].y]=1;
    			}
    		}
    		REP(j,1,n) {
    			if (s[1].size()+tot<i&&!vis[a[j].y]) {
    				++tot, c+=a[j].x;
    			}
    		}
    		if (s[1].size()+tot==i) { 
    			ans = min(ans, c);
    		}
    		REP(i,1,n) vis[i]=0;
    	}
    	printf("%lld\n", ans);
    }

转载于:https://www.cnblogs.com/uid001/p/10411614.html

发表评论取消回复

表情：

评论列表（有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

相关 codeforces C. Sorting Railway Cars 贪心

C. Sorting Railway Cars time limit per test 2 seconds memory limit per test 256 mega

梦里梦外;/ 2022年08月18日 15:22/ 0 赞/ 3 阅读

相关 codeforces 603 C. Load Balancing 贪心

C. Load Balancing time limit per test 2 seconds memory limit per test 256 megabytes

清疚/ 2022年08月18日 15:22/ 0 赞/ 52 阅读

相关 codeforces C. Bits 贪心

C. Bits time limit per test 1 second memory limit per test 256 megabytes input sta

偏执的太偏执、/ 2022年07月24日 09:16/ 0 赞/ 185 阅读

相关 codeforces C. Money Transfers 贪心

C. Money Transfers time limit per test 1 second memory limit per test 256 megabytes

怼烎@/ 2022年07月24日 08:14/ 0 赞/ 170 阅读

相关 C - Hot Bath CodeForces - 127C——贪心

Think: 1>题意：已知冷水温度t1,热水温度t2,冷水最高释放速度x1,热水最高释放速度x2,问如何控制释放速度可使最快达到正趋向于温水温度t0 1>题意建模：两

矫情吗；*/ 2022年06月14日 02:12/ 0 赞/ 141 阅读

相关 CodeForces 873C(贪心)

问题描述: Ivan is playing a strange game. He has a matrix a with n rows and m columns. Eac

深藏阁楼爱情的钟/ 2022年06月07日 12:49/ 0 赞/ 127 阅读

相关 CodeForces 825C(贪心)

问题描述: Makes solves problems on Decoforces and lots of other different online judges. Ea

r囧r小猫/ 2022年06月06日 13:00/ 0 赞/ 140 阅读

相关简单贪心-CodeForces 808C-Tea Party

简单贪心-CodeForces 808C-Tea Party -------------------- 题目链接：[C. Tea Party][] 思路：

心已赠人/ 2022年05月16日 06:38/ 0 赞/ 167 阅读

相关 Codeforces 353E 贪心

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。思路：容易发现，如果某个边的集合点的数目大于等于2，那么

妖狐艹你老母/ 2021年12月12日 02:04/ 0 赞/ 225 阅读

相关 Elections CodeForces - 1020C (贪心)

大意: 有n个选民, m个党派, 第i个选民初始投$p\_i$一票, 可以花费$c\_i$改变投票, 求最少花费使得第一个党派的票数严格最大假设最终第一个党派得票数$

淩亂°似流年/ 2021年10月01日 00:20/ 0 赞/ 245 阅读