Codeforces Round #503 (by SIS, Div. 2) C. Elections （暴力+贪心）

【题目描述】

　　　　Elections are coming. You know the number of voters and the number of parties — n and m respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give i-th voter ci 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、朴素的环形均分纸牌（暴力枚举环的断点）

【代码】暴力最终选民数

 #include <bits/stdc++.h>

 #define ll long long

 #define pb push_back

 using namespace std;

 int n,m,tot;

 ll ans=LLONG_MAX;

 vector<int> party[];

 int rec[];

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) {

         int p,c; scanf("%d%d",&p,&c);

         party[p].pb(c);

     }

     for(int i=;i<=m;i++) sort(party[i].begin(),party[i].end());

     for(int i=max(,(int)party[].size());i<=n;i++) {

         int cur=party[].size(); ll cost=;

         tot=;

         for(int j=;j<=m;j++) {

             int k;

             for(k=party[j].size();k>=i;k--) cost+=party[j][party[j].size()-k],cur++;

             for(k=party[j].size()-k;k<party[j].size();k++) rec[++tot]=party[j][k];

         }

         if(cur<i) {

             sort(rec+,rec+tot+);

             for(int k=;k<=tot&&cur<i;k++) cost+=rec[k],cur++;

         }

         ans=min(ans,cost);

     }

     printf("%I64d\n",ans);

     return ;

 }

【钓鱼】暴力最终到达的鱼塘

 #include <bits/stdc++.h>

 using namespace std;

 int n,H,ans;

 int b[],dx[],t[];

 int main()

 {

     scanf("%d%d",&n,&H); H=H*/;

     for(int i=;i<=n;i++) scanf("%d",&b[i]);

     for(int i=;i<=n;i++) scanf("%d",&dx[i]);

     for(int i=;i<=n;i++) scanf("%d",&t[i]),t[i]+=t[i-];

     for(int i=;i<=n;i++) {

         int cur=; priority_queue< pair<int,int> > pq;

         for(int j=;j<=i;j++) pq.push(make_pair(b[j],dx[j]));

         int T=H-t[i];

         while(pq.top().first>&&T>) {

             cur+=pq.top().first; T--;

             pair<int,int> p=pq.top(); pq.pop();

             p.first-=p.second; pq.push(p);

         }

         ans=max(ans,cur);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

Codeforces Round #503 (by SIS, Div. 2) C. Elections （暴力+贪心）

最新文章

热门文章