codeforces-458c-Elections-前k大线段树

题目链接
题意：现在有个小镇要选举，有n个村民，每个村民给出他选举的人ai，你可以贿赂一个村民来选你，花费为bi。选上的条件为你的选票数严格大于任何一个备选人，现在问你要选上的最小话费为多少。

思路：枚举自己需要多少得票数x，把所有大于x的候选人的最便宜的票都买了，保证他小于x，这时候如果票还不够，就再买前k小的票，k为x-当前票。
在枚举x的时候，可以从大到小枚举，用一个vector g[n]先把所有人大于i（i=1,2……n）的票数所要的钱从小到大预处理存起来，那么枚举到x的时候，可以直接用上一个sum1的结果加上∑g[x][i]（i=0,1……）得到，之后再在线段树里求前k大的和就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
struct node
 {int l,r,sum,cnt;
 	}tr[400040];
vector<int>a[100005],g[100005];
int i,j,k,m,n,t,x,y; 
int cost;
int cnt;
void build(int L,int R,int num)
 {tr[num].l=L;
  tr[num].r=R;
  if(L==R)
   {tr[num].sum=0;
    tr[num].cnt=0;
   }
  else
   {build(L,(L+R)/2,2*num);  
    build((L+R)/2+1,R,2*num+1);
    tr[num].sum=tr[num*2+1].sum+tr[num*2].sum;  
    tr[num].cnt=tr[num*2+1].cnt+tr[num*2].cnt;
   }
 } 
  
  
void add(int x,int y,int num)
  { 
    if(tr[num].l==tr[num].r)
    {
     tr[num].sum+=x*y;
     tr[num].cnt+=y; 
     return ;
	}
  	if(x>(tr[num].l+tr[num].r)/2)add(x,y,num*2+1);  
  	if(x<=(tr[num].l+tr[num].r)/2)add(x,y,num*2);
	tr[num].sum=tr[num*2+1].sum+tr[num*2].sum;  
    tr[num].cnt=tr[num*2+1].cnt+tr[num*2].cnt;
	 }  
int query(int k,int num)
 { if(k<0)return 0;
   if(tr[num].cnt<=k)return tr[num].sum;
   if(tr[num].l==tr[num].r)
    return min(k,tr[num].cnt)*tr[num].l;
   if(tr[num*2].cnt>=k)
    return query(k,num*2);
	else
	 return tr[num*2].sum+query(k-tr[num*2].cnt,num*2+1); 
     
 }
	
int main()
 {
 	scanf("%d",&n);
 	build(0,100004,1);
 	cnt=0,cost=0;
 	for(int i=0;i<=100000;i++)
 	{
 		a[i].clear();
	    g[i].clear(); 
	}
 	for(int i=1;i<=n;i++)
 	{
 	  int u,v;
	  scanf("%d%d",&u,&v);
	  a[u].push_back(v);
	  add(v,1,1);
	}
	/*while(1)
	{
		scanf("%d",&k);
		printf("%d\n",query(k,1));
	}*/
	for(int i=0;i<=100002;i++)sort(a[i].begin(),a[i].end());
	
	for(int i=0;i<=100002;i++)
	 for(int j=0;j<a[i].size();j++)
	  g[a[i].size()-j].push_back(a[i][j]);
	/*for(int i=1;i<=n;i++)
	printf("%d:%d\n",i,g[i].size());*/  
	int minn=1e9+1; 
	for(int i=n;i>=0;i--)
	{  
	 	for(int j=0;j<g[i].size();j++)
	 	{
	 		cost+=g[i][j];
	 		cnt++;
	 		add(g[i][j],-1,1);
		}
		//printf("query:%d\n",query(1,1)); 
	    if(cnt>=i)minn=min(minn,cost);
		 else minn=min(minn,query(i-cnt,1)+cost);	 
		//printf("x:%d cnt:%d cost:%d minn:%d\n",i,cnt,cost,minn); 
	}
	printf("%d\n",minn);  
 return 0;	
}