首页 > 试题广场 >

社团主席选举

[编程题]社团主席选举
  • 热度指数:2075 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

一共有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要n票当选 那么其他人多余n-1票的就都要收买 如果把所有超过n-1票的都收买了 如果这时1号还没有n票 那就从不是投1号和刚刚没有收买的人中从小到***人 直道1号满n票这就是这个方案要花的糖 如果把超过n-1票的都收买了 1号超过了n票 就说明其实1号并不需要n票 并且小于n的也不可能是答案 只要把满足第一个条件的所要花费的糖求个最小值就是答案 复杂度O(n*m)
/**
**      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;
}

编辑于 2019-07-17 07:53:32 回复(2)
//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);
    }
}
发表于 2019-06-27 10:38:11 回复(0)
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)

发表于 2019-06-26 14:54:56 回复(0)
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;
    }



}
用例通过率: 90.00% 运行时间: 138ms 占用内存: 19312KB(没有暗箱操作~)
发表于 2020-08-23 15:31:19 回复(0)
#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;
}

发表于 2019-12-21 01:32:45 回复(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;
}

发表于 2019-07-18 21:27:00 回复(4)
搞不清楚为什么只有70%

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

//找到获得支持最多的那个人
int findMax(unordered_map<int, int>& mp){
    int maxMan = 0, maxNum = 0;
    unordered_map<int, int>::iterator it = mp.begin();
    while (it != mp.end()){
        if (it->second >= maxNum){
            maxNum = it->second;
            maxMan = it->first;
        }
        ++it;
    }
    return maxMan;
}

//找到需要糖果最少的那个人
int minCandy(const vector<vector<long long>>& arrs){
    static int i = 0;
    for (;i<arrs.size();++i){
        if (arrs[i][0] != 1)
            return i;
    }
    return -1;
}

int main(){
    //输入
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> arrs(n);
    unordered_map<int, int> mp;
    for (int i=0;i<n;++i){
        long long temp1,temp2;
        cin >> temp1 >> temp2;
        arrs[i].push_back(temp1);
        arrs[i].push_back(temp2);
        ++mp[temp1];
    }
    
    long long candy = 0;
    //对所有人根据所需糖果从小往大排序
    sort(arrs.begin(),arrs.end(),
         [](const vector<long long>& a, const vector<long long>& b){
             return a[1] < b[1];
         });
    
    int i = 0;
    while (true){
        //找到最被人支持的那个人
       int maxMan = findMax(mp);
        //如果支持人数最多的人是1,就退出
       if (maxMan == 1)
           break;
        else{
            //找到最少的那个人
            long long change = minCandy(arrs);
            if (change < 0) continue;
            //给他糖
            candy += arrs[change][1];
            //他改为支持1
            --mp[arrs[change][0]];
            arrs[change][0] = 1;
            ++mp[1];
        }
    }
    
    cout << candy << endl;
    return 0;
}


发表于 2020-07-15 17:38:00 回复(1)
只通过了90%,不通过应该是哪里漏了吧
var one_line=readline().split(' ').map(Number);
//投票者人数
var person=one_line[0]; //5
//候选人数
var wait=one_line[1]; //5
// 候选人票数数组 [0,0,0,0,0]
function add_str(str,num){
    var as=''
    for(var i=0;i<num;i++){
        as=as+str;
    }
    return as;
}
var a_per=add_str('0',wait).split('').map(Number);//[0,0,0,0,0]
//代价数组
var arr=[];  //[[2,5],[3,5],[4,5],[5,6],[5,1]]
for(var i=0;i<person;i++){
    var two_line=readline().split(' ').map(Number);
    arr.push(two_line);
    //统计票数
    a_per[two_line[0]-1]++;//[1,1,1,1,2]
}
// 需要帮忙的是1号!
// 思路: 循环数组,计算每一个候选人票数,循环计算最大值及候选人
// 循环遍历(按照代价排序),首先拉拢代价最小且价值最大的人(拉拢投最大候选人的人才是价值最大的)
// 也就是所需票数>1时都是优先拉拢投最大候选人的人,代价=代价/2
var max=[1,a_per[0]]
for(var j=0;j<wait;j++){
    if(a_per[j]>max[1]){
        // 加一是因为投票索引从1开始
        max=[j+1,a_per[j]];//[5,2]
    }
}
//计算代价数组
for(var q=0;q<person;q++){
    //首先增加投最大候选人的人的价值(减小糖果数)
    if(arr[q][0]==max[0]){
        arr[q][1]=arr[q][1]/2;
    }
}
for(var k=0;k<person;k++){
    //冒泡排序
    for(var w=0;w<person-k-1;w++){
        if(arr[w][1]>arr[w+1][1]){
            var tem=arr[w];
            arr[w]=arr[w+1];
            arr[w+1]=tem;//[[5,0.5],[5,3],[2,5],[3,5],[4,5]]
        }
    }
}
//票数数组是 a_per[two_line[0]-1]++;//[1,1,1,1,2]
//糖果数
var min=0;
for(var p=0;p<person;p++){
    if(max[0]==1){
        break;
    }
    if(a_per[0]>max[1]){
        break;
    }
    //如果只差一票就能让1号当选,并且下一个投票者不是投max候选人并且代价<当前代价*2那就选下一个投票者,否则继续
    if(max[0]==arr[p][0]&&max[1]-1<=a_per[0]){
        if(arr[p+1]&&arr[p][1]*2<arr[p+1][1]){
            max[1]--;
            a_per[0]++;
            min+=arr[p][1]*2;
        }else{
            if(arr[p+1]&&arr[p+1][0]!=max[0]){
                a_per[0]++;
                min+=arr[p+1][1];
            }else{
                max[1]--;
                a_per[0]++;
                min+=arr[p][1]*2;
            }
        }
    }else if(max[0]==arr[p][0]){
        max[1]--;
        a_per[0]++;
        min+=arr[p][1]*2;
    }else if(max[0]!=arr[p][0]){
        a_per[0]++;
        min+=arr[p][1];
    }
    //console.log(min)
}
print(min)


发表于 2020-02-14 21:23:06 回复(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))
发表于 2019-08-08 15:16:49 回复(2)