http://codeforces.com/problemset/problem/457/C

題意：有n支選票，投給ai，如果要這個人把票投給自己，那么需要花費bi，自己的標號為0。求最少的花費，使得自己選票比選票數(shù)目最多的那個人還要多。

題解：三分

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int save[N]; vector<int> g[N];int cal(int x) {int ans = 0, have = g[0].size(), sn = 0;for (int i = 1; i <= 100000; i++) {int j = 0;if (x <= g[i].size()) {for (; j < g[i].size() - x + 1; j++) {ans += g[i][j];have++;}}for (; j < g[i].size(); j++)save[sn++] = g[i][j];}sort(save, save + sn);for (int i = 0; i < x - have; i++)ans += save[i];return ans; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d", &n);int a, b;for (int i = 0; i < n; i++) {scanf("%d%d", &a, &b);g[a].push_back(b);}for (int i = 1; i <= 100000; i++)sort(g[i].begin(), g[i].end());int l = 1, r = n;while (l < r - 2) {int midl = (l * 2 + r) / 3;int midr = (l + r * 2) / 3;if (cal(midl) > cal(midr)) l = midl;else r = midr;}int ans = INF;for (int i = l; i <= r; i++)ans = min(ans, cal(i));printf("%d\n", ans);//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int save[N]; vector<int> g[N];int cal(int x) {int ans = 0, have = g[0].size(), sn = 0;for (int i = 1; i <= 100000; i++) {int j = 0;if (x <= g[i].size()) {for (; j < g[i].size() - x + 1; j++) {ans += g[i][j];have++;}}for (; j < g[i].size(); j++)save[sn++] = g[i][j];}sort(save, save + sn);for (int i = 0; i < x - have; i++)ans += save[i];return ans; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d", &n);int a, b;for (int i = 0; i < n; i++) {scanf("%d%d", &a, &b);g[a].push_back(b);}for (int i = 1; i <= 100000; i++)sort(g[i].begin(), g[i].end());int l = 1, r = n;while (l < r-1) {int midl = (l + r) >> 1;int midr = (midl + r) >> 1;if (cal(midl) > cal(midr)) l = midl;else r = midr;}printf("%d\n", min(cal(l),cal(r)));//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Elections的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。