Codeforces Round #503 (by SIS, Div. 2)

C.Elections

题型：你们说水题就水题吧...我没有做出来...get到了新的思路，不虚。好像还有用三分做的？

KN Point（注意复杂度性能）：优先队列1，优先队列2

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int inf=3e3+;

 priority_queue<int,vector<int>,greater<int> >tep[inf],s[inf],S; //优先队列

 ll ans=1e18;

 int main()

 {

     ios::sync_with_stdio();

     int n,m;

     cin>>n>>m;

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

     {

         int c,p;

         cin>>c>>p;

         s[c].push(p);

     }

     for(int i=;i<=n;i++)  //索性枚举所有胜出可能需要拥有的票数，就不用考虑到底到底贿赂谁了

     {

         ll v=;int cnt=s[].size();

         while(!S.empty()) S.pop();

         for(int j=;j<=m;j++) tep[j]=s[j];

         for(int j=;j<=m;j++)  //复杂度不会算了，有没有人教一下，感觉整个程序的复杂度在 n^2*log(n)左右

             while(tep[j].size()>=i)

               v+=tep[j].top(),tep[j].pop(),cnt++;  //让所有除1以外的所有人需要减掉的票数

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

             while(!tep[j].empty())

                 S.push(tep[j].top()),tep[j].pop();  //存下剩下的票数

         while(cnt<i&&!S.empty())

             cnt++,v+=S.top(),S.pop();  //用剩下的票数使得1的票数大于等于所需要的票数

         if(cnt>=i) ans=min(ans,v);

     }

     cout<<ans<<endl;

 }

秒客网

Codeforces Round #503 (by SIS, Div. 2)

相关文章