Codeforces Round #503 (by SIS, Div. 2) C. Elections （暴力+贪心）
【题目描述】
Elections are coming. You know the number of voters and the number of parties — bytecoins you can ask him to vote for any other party you choose.
The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.、
【题目链接】
http://codeforces.com/contest/1020/problem/C
【算法】
枚举答案（一号政党最终（至少）的选民数x），其它政党则最终选民数至多为x-1，贪心选取贿赂者。若一号政党仍不足x人，则从剩下的选民中贪心的取。
思想类似的题目：1、（钓鱼）https://loj.ac/problem/10009 （暴力+贪心） 2、朴素的环形均分纸牌（暴力枚举环的断点）
【代码】暴力最终选民数
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 using namespace std; 5 int n,m,tot; 6 ll ans=LLONG_MAX; 7 vector<int> party[3010]; 8 int rec[3010]; 9 int main() 10 { 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) { 13 int p,c; scanf("%d%d",&p,&c); 14 party[p].pb(c); 15 } 16 for(int i=1;i<=m;i++) sort(party[i].begin(),party[i].end()); 17 for(int i=max(1,(int)party[1].size());i<=n;i++) { 18 int cur=party[1].size(); ll cost=0; 19 tot=0; 20 for(int j=2;j<=m;j++) { 21 int k; 22 for(k=party[j].size();k>=i;k--) cost+=party[j][party[j].size()-k],cur++; 23 for(k=party[j].size()-k;k<party[j].size();k++) rec[++tot]=party[j][k]; 24 } 25 if(cur<i) { 26 sort(rec+1,rec+tot+1); 27 for(int k=1;k<=tot&&cur<i;k++) cost+=rec[k],cur++; 28 } 29 ans=min(ans,cost); 30 } 31 printf("%I64d ",ans); 32 return 0; 33 }
【钓鱼】暴力最终到达的鱼塘
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,H,ans; 4 int b[110],dx[110],t[110]; 5 int main() 6 { 7 scanf("%d%d",&n,&H); H=H*60/5; 8 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 9 for(int i=1;i<=n;i++) scanf("%d",&dx[i]); 10 for(int i=2;i<=n;i++) scanf("%d",&t[i]),t[i]+=t[i-1]; 11 for(int i=1;i<=n;i++) { 12 int cur=0; priority_queue< pair<int,int> > pq; 13 for(int j=1;j<=i;j++) pq.push(make_pair(b[j],dx[j])); 14 int T=H-t[i]; 15 while(pq.top().first>0&&T>0) { 16 cur+=pq.top().first; T--; 17 pair<int,int> p=pq.top(); pq.pop(); 18 p.first-=p.second; pq.push(p); 19 } 20 ans=max(ans,cur); 21 } 22 printf("%d ",ans); 23 return 0; 24 }