Elections(CF-1020C)

3219 단어 #수색--폭력 수색CodeForces
Problem Description
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 i-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.
Input
The first line of input contains two integers n and m (1≤n,m≤3000) — the number of voters and the number of parties respectively.
Each of the following n lines contains two integers pipi and cici (1≤pi≤m, 1≤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 1.
Output
Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.
Examples
Input
1 2 1 100
Output
0
Input
5 5 2 100 3 200 4 300 5 400 5 900
Output
500
Input
5 5 2 100 3 200 4 300 5 800 5 900
Output
600
제목: n 개인 투표, 모든 사람이 선택한 번호가 있습니다. 번호를 바꾸려면 반드시 그가 준 가격을 지불해야 합니다. 먼저 1번의 표를 가장 많이 주고 최소한의 돈을 구합니다.
사고방식: 욕심만 생각하면 상황이 너무 많기 때문에 1번의 승리 상태만 고려하고 몇 표로 승리를 얻은 다음에 모든 승리 상황을 일일이 열거하여 가장 좋은 것을 취하면 된다.
Source Program 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 10001
#define MOD 1e9+7
#define E 1e-6
#define LL long long
using namespace std;
struct Node{
    int num;
    int value;
}a[N];
int bucket[N];
int ticket[N];
int cmp(Node x,Node y)
{
    return x.value>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].num,&a[i].value);
        bucket[a[i].num]++;//        
    }

    sort(a+1,a+n+1,cmp);
    long long minn=999999999999,sum=0,ans;
    for(int i=bucket[1];i<=n;i++)//      
    {
        sum=0;
        ans=0;
        for(int j=2;j<=m;j++)
        {
            if(bucket[j]>=i)
            {
                ticket[j]=bucket[j]-i+1;//              
                sum+=ticket[j];//       
            }
            else ticket[j]=0;
        }
        if(i-bucket[1]

자연 병합 정렬 과 단일 체인 시트 구현 의 병합 정렬
714. 거래 수수료로 주식을 사고 팔기 가장 좋은 시간(자바스크립트 솔루션)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage