首先来看题面：

【题目描述】选举拉票

现在你要竞选一个县的县长。你去对每一个选民进行了调查。你已经知道每一个人要选的人是谁，以及要花多少钱才能让这个人选你。要知道现在这个时代，没有百八十万元你是受买不了一个人的$qwq$。现在你想要花最少的钱使得你当上县长。你当选的条件是你的票数比任何一个其它候选人的多（严格的多，不能和他们中最多的相等）。请计算一下最少要花多少钱。

【数据格式】

第一行一个$n$,表示投票者的人数(n<=100000)；

第$2$~$n+1$行,一个$d[i]$表示每一个投票者的投票对象；紧接着一个$p[i]$表示收买这个投票对象需要花多少钱

【简单样例】

$Input$#$1$：$~~~~~~~~~$ $Output$#$1$:

5                        3
1 2
1 2
1 2
2 1
0 0

$Input$#$2$：$~~~~~~~~~$ $Output$#$2$:

10                       3                       
0 0                
3 5
4 6
3 2
4 4
2 1
2 6
0 0
2 4 
3 9

$0$~$10$分做法

对于这个题而言，我们可以马上想到一个很暴力的做法：

将全体投票者的价钱从大到小排序，然后从小到大依次枚举，直到枚举到自己得票数严格大于任何一个人得票数为止。然而对于这个方法，我们可以通过预处理每个竞争对手的得票数，然后在从小到大枚举时,每打算收买一个当前最小价格的人，遍历一遍每个竞争对手的得票，然后判断是否该继续枚举。

看起来这个方法的期望时间复杂度只有$O(n^2)$，并且很有可能常数特别小，平均下来只有大约$40^{-1}$左右,好像对于一般的数据也是能水过的，期望得分$60$~$80$.

但其实，这个方法的$bug$还是蛮严重的，因为其实我只需要稍微修改一下数据，这个方法的贪心就不会总是最优：当我们排好序之后，枚举到第$i$个选民，此时意味着前$i-1$个肯定已经被纳入到收买名单当中；但是这样不一定最优的原因在于，前$i-1$个中有的其实是并不需要加入到集合当中，所以不是最优。

$60$~$80$分做法

对于这个题而言，我们在枚举时可以换一个角度枚举：从枚举人，转变为枚举我需要收买的人数；然后对于每次枚举，我们都从头开始枚举每个选民，并且不断向当前枚举到的收买人数靠近，until相等。这种枚举方式可以使得考虑得更充分，但常数也会相应增大。

那么就会有新·贪心思想：

在枚举时，我们可以考虑如下：要收买这个人，当且仅当他要投的竞争对手票数大于我此次枚举的期望票数，并且价钱一定要为当前最小（满足单调）。这便是新的的贪心策略：排序+判断

那么其实对于这个思想而言，就是首先不断判断每个竞争对手的得票数是否大于此次所枚举的期望得票数，而对于期望得票数，在进行完上述的第一次枚举之后，再进行一次枚举，由于价钱的单调性，很容易让我们找出满足期望得票数的最小价钱。而最终我们可以列举所有的期望得票数，从中选取一个最小的价钱即为答案。

代码大概长这个样子

int solve(int x)
{
    memset(num, 0, sizeof(num));
    memset(flag, 0, sizeof(flag));
    for(int i=1;i<=n;i++)
        num[people[i].choice]++;
    int ans=0;
    for(int i=1;i<=n;i++)
        if(people[i].choice!=0 && num[people[i].choice]>=x)
        {
            ans+=people[i].price;
            num[people[i].choice]--;
            num[0]++;
            flag[i]=true;
        }
    for(int i=1;i<=n;i++)
        if(num[0]<x && !flag[i] && people[i].choice!=0)
        {
            ans+=people[i].price;
            num[people[i].choice]--;
            num[0]++;
            flag[i]=true;
        }
    return ans;
}
for(int i=1;i<=n;i++)
res=min(res,solve(i));

这种做法的时间复杂度大约在$O(n^2)$左右，常数应该有优化，但是目测优化好像贡献不是很大，因为本身就附带了一个常数$3$.

$100$分做法

关键点到了，这个题光看题目，我们可以很简单地得到一个结论：最小价钱应当是相对唯一的，即使不唯一也不会重复很多。所以对于价钱$y$和期望收买人数$x$而言，大抵上是满足一个下凸函数的特性，即在一个给定区间内，$y=$ $f(x)$有唯一的最大值或者最小值（此题是最小值）。所以我们了可以考虑三分。

而所谓三分，则是针对一个凸函数的算法，通过不断变换$mid1$、$mid2$、$l$、$r$来找到极值。

但是一般的三分会考虑精度，因为函数运算针对实数，而不是针对整数。但由于这个题的自身特性，我们需要考虑到int类型的精度损失（下取整），所以我们需要人为划定一个不会产生精度误差的边界，即$r-l>k,k>3$

以下为完整代码qwq

#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n;
struct Person
{
    int choice, price;
}people[MAXN];
bool cmp(const Person&A, const Person&B)
{
    return A.price < B.price;
}
int num[MAXN]; 
bool flag[MAXN]; 
int solve(int x) 
{
    memset(num, 0, sizeof(num));
    memset(flag, 0, sizeof(flag));
    for(int i=1;i<=n;i++)
        num[people[i].choice]++;
    int ans=0;
    for(int i=1;i<=n;i++)
        if(people[i].choice!=0 && num[people[i].choice]>=x)
        {
            ans+=people[i].price;
            num[people[i].choice]--;
            num[0]++;
            flag[i]=true;
        }
    for(int i=1;i<=n;i++)
        if(num[0]<x && !flag[i] && people[i].choice!=0)
        {
            ans+=people[i].price;
            num[people[i].choice]--;
            num[0]++;
            flag[i]=true;
        }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>people[i].choice>>people[i].price;
    sort(people+1,people+1+n,cmp);
    int l=1,r=n,mid1,mid2;
    while(l+3<r)
    {
        mid1=l+(r-l)/3;
        mid2=mid1+(r-l)/3;
        if(solve(mid1) > solve(mid2)) l=mid1;
        else r=mid2;
    }
    int pos=l;
    for(int i=l;i<=r;i++)
    if(solve(pos)>solve(i)) pos = i;
    cout << solve(pos) << endl;
}