网易历届笔试题（9）

网易历届笔试题（9）

题目描述

随着又一届学生的毕业，社团主席换届选举即将进行。 

一共有n个投票者和m个候选人，小易知道每一个投票者的投票对象。但是，如果小易给某个投票者一些糖果，那么这个投票者就会改变他的意向，小易让他投给谁，他就会投给谁。 

由于小易特别看好这些候选人中的某一个大神，这个人的编号是1，所以小易希望能尽自己的微薄之力让他当选主席，但是小易的糖果数量有限，所以请你帮他计算，最少需要花多少糖果让1号候选人当选。某个候选人可以当选的条件是他获得的票数比其他任何候选者都多。 

输入描述:

第一行两个整数n和m，表示投票者的个数和候选人的个数。
接下来n行，每一行两个整数x和y，x表示这个投票者的投票对象，y表示需要花多少个糖果让这个人改变意向。
满足1 <= n, m <= 3000，1 <= x <= m，1 <= y <= 109。

输出描述:

一个整数，糖果的最小花费。

示例1

输入

1 2
1 20

输出

0

示例2

输入

5 5
2 5
3 5
4 5
5 6
5 1

输出

6

思路：枚举1号候选人所获得的最大票数，之后将其他大于等于该票数的候选人的票数去掉（我们需要一开始讲投票数组按照第二维从小到大排序，这样才能保证每次剪掉的是花费的最小值），当处理完之后，有可能1号候选人的票数还是不够当前枚举的票数，此时就从小到大遍历投票数组，没有改变意向的票直接用掉即可，直到1号候选人票数够即可。

import java.util.*;
public class Main{public static void main(String[] args){long ans=Long.MAX_VALUE;int n,m,x,y;Scanner in=new Scanner(System.in);n&#Int();m&#Int();int[][] arr=new int[n][2];int[] nums=new int[m+1];for(int i=0;i<n;i++){arr[i][0]&#Int();arr[i][1]&#Int();nums[arr[i][0]]++;}boolean[] used=new boolean[n];Arrays.sort(arr,(a,b)->a[1]-b[1]);int[] now=new int[m+1];for(int i=1;i<=n;i++){if(nums[1]>i)continue;long sum=0;Arrays.fill(used,false);for(int j=1;j<=m;j++)now[j]=nums[j];for(int j=0;j<n;j++){if(arr[j][0]!=1 && now[arr[j][0]]>=i){used[j]=true;sum+=arr[j][1];now[arr[j][0]]--;now[1]++;}}for(int j=0;j<n && now[1]<i;j++){if(used[j] || arr[j][0]==1) continue;now[1]++;sum+=arr[j][1];}ans=Math.min(ans,sum);}System.out.println(ans);}
}