随着又一届学生的毕业,社团主席换届选举即将进行。
一共有n个投票者和m个候选人,小易知道每一个投票者的投票对象。但是,如果小易给某个投票者一些糖果,那么这个投票者就会改变他的意向,小易让他投给谁,他就会投给谁。
由于小易特别看好这些候选人中的某一个大神,这个人的编号是1,所以小易希望能尽自己的微薄之力让他当选主席,但是小易的糖果数量有限,所以请你帮他计算,最少需要花多少糖果让1号候选人当选。某个候选人可以当选的条件是他获得的票数比其他任何候选者都多。
随着又一届学生的毕业,社团主席换届选举即将进行。
一共有n个投票者和m个候选人,小易知道每一个投票者的投票对象。但是,如果小易给某个投票者一些糖果,那么这个投票者就会改变他的意向,小易让他投给谁,他就会投给谁。
由于小易特别看好这些候选人中的某一个大神,这个人的编号是1,所以小易希望能尽自己的微薄之力让他当选主席,但是小易的糖果数量有限,所以请你帮他计算,最少需要花多少糖果让1号候选人当选。某个候选人可以当选的条件是他获得的票数比其他任何候选者都多。
第一行两个整数n和m,表示投票者的个数和候选人的个数。
接下来n行,每一行两个整数x和y,x表示这个投票者的投票对象,y表示需要花多少个糖果让这个人改变意向。
满足1 <= n, m <= 3000,1 <= x <= m,1 <= y <= 109。
一个整数,糖果的最小花费。
1 2 1 20
0
5 5 2 5 3 5 4 5 5 6 5 1
6
/**** 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; } }用例通过率: 90.00% 运行时间: 138ms 占用内存: 19312KB(没有暗箱操作~)
#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; }
#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; }
只过了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))