Elections

C. Elections

证明自己赢的时候获得的票数与贿赂所需的最小代价的函数是一个凸函数：
从自己赢的票数等于 n 的时候往小推，每一次减去一个最大的代价，但是要保证在该情况下能赢

刚开始是单调递增的，但是随着自己的票数越来越少以及某些人的票数越来越多，我们想要自己赢的票数再少一点，那么就应该从票数多的人手上拿票（a）回来，再把自己手上的票（b）（要发给少的人）发出去，因为 a 比 b 先出来，所以 a>b ，所以这个时候自己需要付的钱开始增多了。

因此得证，这是一个凸函数。

代码：

// Created by CAD on 2020/1/13.
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int maxn=1e5+5;
vector<int> a[maxn];
int n,MAX;
int judge(int mid)
{
    int cnt=mid-a[0].size();
    vector<int> rest;
    int money=0;
    for(int i=1; i<=MAX; ++i)
    {
        int j;
        for(j=0;j<=(int)a[i].size()-mid;++j)
            money=money+a[i][j],cnt--;
        for(;j<a[i].size();++j)
            rest.push_back(a[i][j]);
    }
    if(cnt<0) return inf;
    sort(rest.begin(),rest.end());
    for(int i=0;i<cnt;++i)
        money+=rest[i];
    return money;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int x,y;    cin>>x>>y;
        MAX=max(MAX, x);
        a[x].push_back(y);
    }
    if(n==1) {
        cout<<a[MAX][0]<<endl;return 0;
    }
    for(int i=1; i<=MAX; ++i)
        sort(a[i].begin(),a[i].end());
    int l=0,r=n,ans=inf;
    while(l<=r-1)
    {
        int mid=(l+r)>>1;
        int midmid=(r+mid)>>1;
        int ans1=judge(mid),ans2=judge(midmid);
        if(ans1<=ans2) ans=min(ans,ans1),r=midmid;
        else ans=min(ans,ans2),l=mid;
    }
    cout<<ans<<endl;
    return 0;
}