cf 1020 C
2 seconds
256 megabytes
standard input
standard output
As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.
Elections are coming. You know the number of voters and the number of parties — nn and mm respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give ii-th voter cici bytecoins you can ask him to vote for any other party you choose.
The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.
The first line of input contains two integers nn and mm (1≤n,m≤30001≤n,m≤3000) — the number of voters and the number of parties respectively.
Each of the following nn lines contains two integers pipi and cici (1≤pi≤m1≤pi≤m, 1≤ci≤1091≤ci≤109) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.
The United Party of Berland has the index 11.
Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.
1 2
1 100
0
5 5
2 100
3 200
4 300
5 400
5 900
500
5 5
2 100
3 200
4 300
5 800
5 900
600
In the first sample, The United Party wins the elections even without buying extra votes.
In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties 33, 44 and 55 get one vote and party number 22 gets no votes.
In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
using namespace std;
#define ll long long
#define gep(i,a,b) for(int i=a;i<=b;i++)
#define gepp(i,a,b) for(int i=a;i>=b;i--)
#define gep1(i,a,b) for(ll i=a;i<=b;i++)
#define gepp1(i,a,b) for(ll i=a;i>=b;i--)
#define N 3009
#define ph push_back
#define inf 10000000000000098
vector<int>ve[N];
int n,m;
ll MIN;
ll solve(ll x){
vector<int>se;
ll ret=,cnt=ve[].size();//初始值
gep(i,,m){
int num=ve[i].size();
gep(j,,num-){
if(num-j>=x){//严格大
ret+=ve[i][j];//必须加到party1上,因为加到别的上面,最后还是加到1上。
cnt++;
}
else{
se.ph(ve[i][j]);
}
}
}
if(cnt<x){
sort(se.begin(),se.end());
for(int i=;i<se.size()&&cnt<x;i++){//在从se里找
ret+=se[i];
cnt++;
}
}
//cnt最后一定是>=x的
return ret;
}
int main()
{
int x;
ll y;
scanf("%d%d",&n,&m);
gep(i,,n){
scanf("%d%lld",&x,&y);
ve[x].ph(y);
}
gep(i,,m)
sort(ve[i].begin(),ve[i].end());
MIN=inf;
gep(i,,n){//枚举查找,不能用二分
MIN=min(MIN,solve(i));
}
printf("%lld\n",MIN);
return ;
}
最新文章
- Spire.Pdf 的各种操作总结
- 怎么才能算大项目(Application),大的衡量?
- 深入理解SQL的四种连接-左外连接、右外连接、内连接、全连接(转)
- docker命令小记
- svn 提交失败
- tcpprep 对IPV6的支持
- React-Native首次运行提示-ReferenceError-Can-t-find-variable-fbBatchedBridge
- 6.Hibernate单向的多对一 关联映射
- java环境安装之不能安装exe文件
- ovs + kernel datapath 的分片与重组流程
- JavaScript:window.onload问题
- php-cgi占用太多cpu资源而导致服务器响应过慢
- jQuery_parent() parents() closest()区别
- 一个判断男女性别的JS脚本
- oracle 常用字符串函数
- 关于W8.1不能安装VS2015(包括2017等)
- HDU 5810 Balls and Boxes 数学
- vue 笔记1
- mysql show variables
- iOS开发之静态库.a 以及合并