题意：贿赂选举人使得自己成功获选， 现在求得最小花费是多少。
题解：我们可以发现他是一个凹型函数， 我们用三分去找最小值就好了。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<queue> 5 #include<vector> 6 #include<algorithm> 7 #include<cmath> 8 #include<iomanip> 9 #include<cstdio> 10 #define LL long long 11 #define ULL unsigned LL 12 #define lson l,m,rt<<1 13 #define rson m+1,r,rt<<1|1 14 #define fi first 15 #define se second 16 using namespace std; 17 const int N = 1e5+5; 18 vector<int> son[N]; 19 int lt[N]; 20 int cal(int x){ 21 int need = x - son[0].size(); 22 int cnt = 0, ret = 0; 23 for(int i = 1; i < N; i++){ 24 for(int j = 0; j < son[i].size(); j++){ 25 if(son[i].size() - j >= x){ 26 ret += son[i][j]; 27 need--; 28 } 29 else lt[cnt++] = son[i][j]; 30 } 31 } 32 if(need <= 0) return ret; 33 sort(lt, lt+cnt); 34 for(int i = 0; i < need; i++) ret += lt[i]; 35 return ret; 36 } 37 int main(){ 38 int n, u, v; 39 scanf("%d",&n); 40 for(int i = 1; i <= n; i++){ 41 scanf("%d%d",&u,&v); 42 son[u].push_back(v); 43 } 44 for(int i = 1; i < N; i++) sort(son[i].begin(), son[i].end()); 45 int l = 0, r = n; 46 while(l+2 < r){ 47 int m1 = l+r >> 1; 48 int m2 = m1+r >> 1; 49 if(cal(m1) > cal(m2)) l = m1; 50 else r = m2; 51 //printf("%d %d %d %d ",m1, m2, l, r); 52 } 53 int ans = cal(l); 54 for(int i = l+1; i <= r; i++) ans = min(ans,cal(i)); 55 printf("%d ", ans); 56 return 0; 57 }