题目

传送门

思路

我们考虑直接枚举最后的票数

因为我们已知最后的票数，

先处理超过这个票数的党派

如果不够的话再贪心的选择即可

注意不保证\(n>m\)

代码

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int id;
    long long w;
    friend bool operator < (const node &a,const node &b)
    {
        return a.w<b.w;
    }
};
int n,m;
int _ind;
int s1[3005];
int s2[3005];
node a[3005];
bool vis[3005];
long long ret=0;
long long ans=(1ll<<60);
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].id>>a[i].w;
        s1[a[i].id]++;
    }
    sort(a+1,a+n+1);
    for(int i=s1[1];i<=n;i++)
    {
        _ind=1;
        ret=0;
        for(int j=1;j<=n;j++)
            vis[j]=0;
        for(int j=1;j<=m;j++)
            s2[j]=s1[j];
        for(int j=1;j<=n;j++)
        {
            if(s2[a[j].id]>=i&&a[j].id!=1)
            {
                vis[j]=1;
                s2[1]++;
                s2[a[j].id]--;
                ret+=a[j].w;
            }
        }
        while(s2[1]<i)
        {
            while(vis[_ind]==1||a[_ind].id==1)
                _ind++;
            s2[1]++;
            ret+=a[_ind].w;
            _ind++;
        }       
        ans=min(ans,ret);
    }
    cout<<ans;
    return 0;
}

习题： Elections

原文：https://www.cnblogs.com/loney-s/p/12261444.html