1020C Elections
2024-10-21 13:32:13
题目大意
现在有 n个人,m个党派,第i个人开始想把票投给党派pi,而如果想让他改变他的想法需要花费ci元。你现在是党派1,问你最少花多少钱使得你的党派得票数大于其它任意党派。
分析
我们枚举i,表示除了自己之外的其它任何党派最多得票数不超过i,而我们每次只需要改变一个党派中需要花费的钱最少的那几个人就行了,在保证其它党派德比得票数都小于i之后如果自己党派的得票小于i,则不断改变需花费钱最少的那一个人的想法就行了。详见代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define li long long
const li inf = 1e18;
struct node {
int a;
li b;
};
node d[];
inline bool cmp(const node x,const node y){
return x.b<y.b;
}
int used[],tot[];
int main(){
int n,m,i,j,k;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++){
scanf("%d%lld",&d[i].a,&d[i].b);
}
sort(d+,d+n+,cmp);
li ans=inf;
for(i=;i<=n;i++){
memset(used,,sizeof(used));
memset(tot,,sizeof(tot));
li sum=;
for(j=n;j>;j--)
if(d[j].a!=){
if(tot[d[j].a]+>=i){
tot[]++;
used[j]=;
sum+=d[j].b;
}else {
tot[d[j].a]++;
}
}else {
tot[]++;
used[j]=;
}
for(j=;j<=n;j++)
if(!used[j]&&tot[]<i){
tot[]++;
sum+=d[j].b;
}
if(tot[]>=i)ans=min(ans,sum);
}
cout<<ans<<endl;
return ;
}
最新文章
- C#开机自动启动程序代码
- 使用grep恢复被删除文件内容【转】
- 通过HTML5实现发送声音
- C#中的操作数据库的SQLHelper类
- PHP中静态方法和非静态方法的相互调用
- JNLP(Java Web Start )(转)
- CI框架 .htaccess 隐藏url在index.php解决方案
- js cookie 记住用户名密码
- 【Maven】构建war包时排除web.xml
- vue常考面试题
- .net排坑篇:负载均衡域名转发的背后
- springboot-admin自定义事件通知
- Series.str——字符串批量处理方法
- 学习笔记50—多重假设检验与Bonferroni校正、FDR校正
- HDFS-异常大全-《每日五分钟搞定大数据》
- Ubuntu x86-64汇编(6)
- linux 实践到的命令 collection
- Spring集成quartz集群配置总结
- JQuery中serialize()
- C# 获取SHA256码
热门文章
- 微信浏览器HTTP_USER_AGENT判断
- 剑指offer--3.用两个栈实现队列
- 2017.11.28 Enginering management:problem-solving ability
- loj #161 子集卷积
- 转载:电商项目完成的BUG调查原因和解决方案
- LeetCode Maximum Average Subarray I
- LeetCode Reverse String II
- 使用python实现两个文件夹里文件的对比(包含内容的对比)
- nodejs 不同请求获取前端传的参数
- 使用while 打印10~1,1~10