收藏
关注现在你要竞选一个县的县长。你去对每一个选民进行了调查。你已经知道每一个人要选的人是谁，以及要花多少钱才能让这个人选你。现在你想要花最少的钱使得你当上县长。你当选的条件是你的票数比任何一个其它候选人的多（严格的多，不能和他们中最多的相等）。请计算一下最少要花多少钱。
Input
单组测试数据。
第一行有一个整数n (1 ≤ n ≤ 10^5)，表示这个县的选民数目。
接下来有n行，每一行有两个整数ai 和 bi (0 ≤ ai ≤ 10^5; 0 ≤ bi ≤ 10^4)，表示第i个选民选的是第ai号候选人，想要让他选择自己就要花bi的钱。你是0号候选人（所以，如果一个选民选你的话ai就是0，这个时候bi也肯定是0）。
Output
输出一个整数表示花费的最少的钱。
Input示例
5
1 2
1 2
1 2
2 1
0 0
Output示例
3 思路：
线段树+扫描线思想
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const ll M = 1e5 + ;
vector<ll>g[M];
vector<ll>rk[M];
ll sum[M<<],num[M<<];
void pushup(ll rt){
num[rt] = num[rt<<] + num[rt<<|];
sum[rt] = sum[rt<<|] + sum[rt<<];
} void update(ll p,ll l,ll r,ll rt){
if(l == r){
sum[rt] += l;
num[rt] ++;
return ;
}
ll m = (l + r) >> ;
if(p <= m) update(p,lson);
else update(p,rson);
pushup(rt);
} ll query(ll p,ll l,ll r,ll rt){
if(l == r)
return l*p;
ll m = (l + r) >> ;
if(p == num[rt<<]) return sum[rt<<];
else if(p < num[rt<<]) return query(p,lson);
else return sum[rt<<] + query(p - num[rt<<],rson);
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
ll n,u,v;
ll mx = ,ans = ;
cin>>n;
for(ll i = ;i <= n;i ++){
cin>>u>>v;
if(v == ) continue;
ans += v;
mx = max(mx,v);
g[u].push_back(v);
}
for(ll i = ;i <= M;i ++){
if(g[i].size()){
sort(g[i].begin(),g[i].end(),greater<ll>());
for(ll j = ;j < g[i].size();j ++){
rk[j].push_back(g[i][j]);
}
}
}
ll nn = n;
ll minn = ans,cnt = ;
for(ll i = ;i < n;i ++){
nn -= rk[i].size();
if(rk[i].size()==) continue;
for(ll j = ;j < rk[i].size();j ++){
ans -= rk[i][j];
update(rk[i][j],,mx,);
}
if(nn <= i+){
cnt = query(min(n,i+-nn),,mx,);
}
minn = min(minn,ans+cnt);
}
cout<<minn<<endl;
}