社团主席选举

	/**



	**      author:XiaKIsGod



	**      time:2019.4



	**/



	#include <bits/stdc++.h>



	#define LL long long



	#define pb push_back



	#define endl "\n"



	#define FIN freopen("2.in","r",stdin)



	#define mem(x,v) memset(x,v,sizeof(x))



	#define rep(i,a,n) for(int i=a;i<n;i++)



	#define per(i,a,n) for(int i=n-1;i>=a;i--)



	using namespace std;



	const int N = 30100;



	const LL MAX = 10000000000000;



	int n,m,cnt,step;



	LL ans = MAX;



	LL res;



	struct P{



	    int idx,x; 



	    LL y;



	    bool operator < (constP& rhs) const{    



	        return y < rhs.y;



	    }



	}p[N];



	vector<P> G[N];



	bool vis[N];



	LL check(int sum){



	    mem(vis,0);



	    cnt = sum - G[1].size();



	    res = 0;



	    rep(i,2,m+1){



	        step = G[i].size()-sum+1;



	        rep(j,0,step){



	            cnt--;



	            res+=G[i][j].y;



	            vis[G[i][j].idx] = 1;



	        }



	    }



	    if(cnt<0) return MAX;



	    rep(i,0,n){



	        if(cnt==0) break;



	        if(p[i].x==1||vis[p[i].idx])continue;



	        cnt--;



	        res+=p[i].y;



	        vis[p[i].idx] = 1;



	    }



	    return res;



	}



	int main()



	{



	    ios::sync_with_stdio(false);



	    cin>>n>>m;



	    rep(i,0,n){



	        p[i].idx = i;



	        cin>>p[i].x>>p[i].y;



	    }



	    sort(p,p+n);



	    rep(i,0,n) G[p[i].x].pb(p[i]);



	    int l = G[1].size();



	    int r = n/2+1;



	    per(i,l,r+1){



	    LL an = check(i);



	    if(an==MAX) break;



	    ans = min(an,ans);



	    }



	    cout<<ans<<endl;



	    return0;



	}

//package 网易2019_A;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author     ：
 * @date       ：2019/6/25 0025
 * @description:
 * 参考@XiaKIsGod的c版本，写了java版本。
 * 思路就是暴力枚举：
 * 这个哥们当选，至少得到k张票，分以下两种情况
 * 1.暗箱操作每个大于等于k的候选者多余的票，如果暗香操作完了，则continue，否则，转2；
 * 2.把剩下的所有没有被暗箱操作的票聚集起来，排个序，一个一个取，直到候选者的票大于等于k；
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 多少张票
        int voteNum = in.nextInt();
        // 多少个候选者
        int peopleNum = in.nextInt();
        // 每个候选者的票
        int[] voteNumOfPeople = new int[peopleNum];
        // 暗箱操作某个候选者的票消耗的糖果
        List<Integer>[] cost = new ArrayList[peopleNum];
        for (int i = 0; i < peopleNum; i++) {
            cost[i] = new ArrayList<>();
        }
        // 最后的结果
        long res = Integer.MAX_VALUE;
        // 读每张票，存入cost和voteNumOfPeople
        for (int i = 0; i < voteNum; i++) {
            int peopleTemp = in.nextInt() - 1;
            int costTemp = in.nextInt();
            voteNumOfPeople[peopleTemp]++;
            cost[peopleTemp].add(costTemp);
        }
        // 每个候选者暗香操作的糖果排序
        for (int i = 1; i < peopleNum; i++) {
            Collections.sort(cost[i]);
        }
        // 开始暴力枚举 这哥们至少i张票才能入选
        for (int i = 1; i <= voteNum; i++) {
            long costNum = 0;
            List<Integer> costTempList = new ArrayList<>();
            // 需要多少票
            int needVote = i - voteNumOfPeople[0];
            // 准备统计票数≥i的
            for (int j = 1; j < peopleNum; j++) {
                if (voteNumOfPeople[j] >= i) {
                    int temp = voteNumOfPeople[j] - i + 1;
                    for (int k = 0; k < temp; k++) {
                        costTempList.add(cost[j].get(k));
                    }
                }
            }
            for (int j = 0; j < costTempList.size(); j++) {
                needVote--;
                costNum += costTempList.get(j);
            }
            // 光削大头的就够了，就直接返回
            if (needVote <= 0) {
                res = Math.min(res, costNum);
                continue;
            }
            // 光操作≥i选票的还不行，在剩下的人中继续抽
            costTempList = new ArrayList<>();

            for (int j = 1; j < peopleNum; j++) {
                // 准备统计票数≥i的剩下的部分
                if (voteNumOfPeople[j] >= i) {
                    int temp = voteNumOfPeople[j] - i + 1;
                    for (int k = temp; k < cost[j].size(); k++) {
                        costTempList.add(cost[j].get(k));
                    }
                } else {
                    // 票数没超过i的
                    costTempList.addAll(cost[j]);
                }
            }
            Collections.sort(costTempList);
            // 票数不够继续补
            for (int j = 0; j < costTempList.size(); j++) {
                needVote--;
                costNum += costTempList.get(j);
                if (needVote <= 0) {
                    res = Math.min(costNum, res);
                    break;
                }
            }
        }
        System.out.println(res);
    }
}

	

import heapq
n,m=map(int,input().split())
g=[list() for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    g[a].append(b)
c,p,res,base,count=0,len(g[1]),999999999,0,0
for l in g:
    c=max(c,len(l))
    if len(l)==len(g[1]):
        count+=1
    l.sort()
if c==len(g[1]) and count==1:
    print(0)
else:
    for i in range(c+1,-1,-1):
        h=[]
        for j in range(2,len(g)):
            if len(g[j])==i:
                base+=g[j].pop(0)
                p+=1
            if g[j]:
                heapq.heappush(h,(g[j][0],j))
        if p>=i:
            res=min(res,base)
            break
        else:
            v=[1]*(m+1)
            k,tem=i-p,0
            while k>0:
                t=heapq.heappop(h)
                tem+=t[0]
                if v[t[1]]<len(g[t[1]]):
                    heapq.heappush(h,(g[t[1]][v[t[1]]],t[1]))
                    v[t[1]]+=1
                k-=1
            res=min(res,base+tem)
    print(res)

import java.util.*;

public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        HashMap<Integer, Integer> map = new HashMap<>();
        long[][] ticket = new long[n][2];
        for (int i = 0; i < n; i++) {
            ticket[i][0] = sc.nextInt();
            ticket[i][1] = sc.nextInt();
            int cur = (int) ticket[i][0];
            if (map.containsKey(cur)) {
                map.put(cur, map.get(cur) + 1);
            } else {
                map.put(cur, 1);
            }
        }

        long cost = 0;
        while (!isOK(map)) {
            int now = findMin(ticket, n);
            map.put((int)ticket[now][0],map.get((int)ticket[now][0])-1);
            map.put(1,map.getOrDefault(1,0)+1);
            cost += ticket[now][1];
            ticket[now][0] =1;
        }
            System.out.println(cost);
    }

    public static int findMin(long[][] src,int n){
        int target =0;
        while (src[target][0]==1){
            target++;
            if (target==n-1) return n-1;
        }
        for (int i =target;i<n;i++){
            if (src[i][0]!=1&&src[i][1]<src[target][1]){
                target =i;
            }
        }
        return target;
    }


    public static boolean isOK(Map<Integer,Integer> map){
        int cur_T =map.getOrDefault(1,0);
        Set<Integer> keys =map.keySet();
        for (int key:keys){
            if (key!=1&&map.get(key)>=cur_T) return false;
        }
        return true;
    }



}

#include <bits/stdc++.h>
using namespace std;

const int N = 3003;
int n, m, Min=INT_MAX;
map<int, int> cnt;
bool vis[N];

struct P{
    int x,y;
}p[N];

int FindMost(){
    int k, t=0;
    for(int i=m;i>0;i--){
        if(cnt[i] > t){
            t = cnt[i];
            k = i;
        }
    }
    return k;
}

int F1(){
    int k, t=INT_MAX;
    for(int i=0;i<n;i++){
        if(vis[i])
            continue;
        if(t > p[i].y){
            t = p[i].y;
            k = i;
        }
    }
    return k;
}

int F2(int c){
    int k, t=INT_MAX;
    for(int i=0;i<n;i++){
        if(vis[i])
            continue;
        if(p[i].x == c){
            if(t > p[i].y){
                t = p[i].y;
                k = i;
            }
        }
    }
    return k;
}

void DFS(int sum){
    if(sum >= Min)
        return;
    int a[2];
    int c = FindMost();
    if(c == 1){
        if(sum < Min)
            Min = sum;
        return;
    }
    a[0] = F1();
    a[1] = F2(c);
    for(int i=0;i<2;i++){
        if(i==1 && a[1]==a[0])
            return;
        int t = a[i];
        cnt[1]++;
        cnt[p[t].x]--;
        vis[t] = true;
        DFS(sum + p[t].y);
        vis[t] = false;
        cnt[p[t].x]++;
        cnt[1]--;
    }
}

int main(){
    cin>>n>>m;
    memset(vis, false, sizeof(vis));
    for(int i=0;i<n;i++){
        cin>>p[i].x>>p[i].y;
        cnt[p[i].x]++;
    }
    DFS(0);
    cout<<Min<<endl;
    return 0;
}

/*
DFS,每一步有两种选择； 
1、收买花费最少的；2、收买最多得票的支持者中花费最少的
*/
#include <bits/stdc++.h>
using namespace std;
#define N 3001
int n, m;
int x[N], y[N];
bool vis[N];
long ans = LONG_MAX;
unordered_map<int, int> cnt;

int candidate_max()
{//找到最多支持者的*** 
    int candidate = -1, tmp = 0;
    for(int i = m; i > 0; --i) {
        if(cnt[i] > tmp) {
            tmp = cnt[i];
            candidate = i;
        }
    }
    return candidate;
}

pair<int, int> idx_min(int candidate)
{//找到两种选择的投票人的下标 
    int c_min = INT_MAX, t_min = INT_MAX, c_idx, t_idx;
    for(int i = 0; i < n; ++i) {
        if(vis[i]) continue;
        if(t_min > y[i]) {
            t_min = y[i];
            t_idx = i;
        }
        if(x[i] == candidate) {
            if(c_min > y[i]) {
                c_min = y[i];
                c_idx = i;
            }
        }
    }
    return make_pair(t_idx, c_idx);
}

void dfs(long cost)
{
    if(cost >= ans) return;
    int candidate = candidate_max();
    if(candidate == 1) {
        if(cost < ans) ans = cost;
        return;
    }
    pair<int, int> idx = idx_min(candidate);
    // 收买花费最少的
    vis[idx.first] = true;
    cnt[1]++;
    cnt[x[idx.first]]--;
    dfs(cost + y[idx.first]);
    vis[idx.first] = false;
    cnt[1]--;
    cnt[x[idx.first]]++;
    if(idx.first == idx.second) return;
    // 收买最多得票的支持者中花费最少的
    vis[idx.second] = true;
    cnt[1]++;
    cnt[x[idx.second]]--;
    dfs(cost + y[idx.second]);
    vis[idx.second] = false;
    cnt[1]--;
    cnt[x[idx.second]]++;
}

int main(void)
{
//    freopen("input.txt", "r", stdin);
    memset(vis, 0, sizeof(0));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x[i], &y[i]);
        cnt[x[i]]++;
    }
    dfs(0);
    printf("%ld", ans);
    return 0;
}

只过了20%case，不太懂问题在哪

n,m=map(int,input().strip().split())
d={} #用字典存储每个***以及对应的投票人的被收买糖果数
for i in range(n):
    k,v= map(int,input().strip().split())
    if k in d:#判断key值是否已存在
        d[k].append(v)
    else:
        d[k]=[v]
# 统计票数最高的
for i in d.keys():
    candi_max=0
    if len(d[i])>candi_max:
        candi_max=len(d[i])
#大神的票数
if 1 in d.keys():
    vote=int(len(d[1])) 
    del d[1]
else:
    vote=0
candy_all=[] #初始化糖果数存放列表
# 两步操作
for k in range(candi_max+1,0,-1): 
    candy=0
    for i in d.keys():
        while(len(d[i])>=k):
            candy=candy+min(d[i])
            d[i].remove(min(d[i]))
            vote=vote+1
    if vote<k:
        li=[]
        for j in d.keys():
            li.append(d[j])
        li = sum(li,[]) #二维列表压缩成一维
        li.sort() #默认为升序
        if len(li)>0:
            for p in range(0,k-vote):
                candy=candy+li[p]
    candy_all.append(candy)
print(min(candy_all))