글 읽기 - 반례 있을까요...ㅠㅠ

tjwjdgus12 4년 전 0

코드 논리에 이상이 없어보이는데 30%에서 틀렸습니다가 뜹니다...

삼십개정도 테스트 케이스를 더 만들어 해봤는데 이상이 없습니다.

어디서 틀렸을까요 ㅠ

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;

int P, V;

struct Party{
    string name;
    int region_seat;
    int pr_vote;
    
    bool allocation;
    double pr_vote_rate;
    int tmp_yeondong_seat;
    int yeondong_seat;
};

vector<Party> party;
vector<Party>::iterator iter;

void get_input(){
    cin >> P >> V;
    party.resize(P);
    for(int i = 0; i < P; ++i){
        cin >> party[i].name >> party[i].region_seat >> party[i].pr_vote;
    }
}

void judge_allocation(){
    int valid_vote_sum = 0;
    for(iter = party.begin(); iter != party.end(); ++iter){
        valid_vote_sum += iter->pr_vote;
    }
    
    for(iter = party.begin(); iter != party.end(); ++iter){
        bool condition_1 = (iter->pr_vote / (double)valid_vote_sum >= 0.03);
        bool condition_2 = (iter->region_seat >= 5);
        if(condition_1 || condition_2)
            iter->allocation = true;
    }
}

void calc_yeondong(){
    int seat = 47;
    int allocation_vote_sum = 0;
    for(iter = party.begin(); iter != party.end(); ++iter){
        if(iter->allocation){
            seat += iter->region_seat;
            allocation_vote_sum += iter->pr_vote;
        }
        else{
            seat -= iter->region_seat;
        }
    }
    
    int yeondong_seat_sum = 0;
    for(iter = party.begin(); iter != party.end(); ++iter){
        if(iter->allocation){
            double calc;
            iter->pr_vote_rate = (double)iter->pr_vote / allocation_vote_sum;
            calc = (seat * iter->pr_vote_rate - iter->region_seat) / 2.0;
            iter->tmp_yeondong_seat = (calc < 1.0) ? 0 : (int)round(calc);
            yeondong_seat_sum += iter->tmp_yeondong_seat;
        }
    }
    
    if(yeondong_seat_sum == 30){
        for(iter = party.begin(); iter != party.end(); ++iter){
            if(iter->allocation){
                iter->yeondong_seat = iter->tmp_yeondong_seat;
            }
        }
    }
    else if(yeondong_seat_sum < 30){
        int residual = 30 - yeondong_seat_sum;
        yeondong_seat_sum = 0;
        multimap<double, int, greater<double>> prior;
        multimap<double, int, greater<double>>::iterator prior_iter;
        for(iter = party.begin(); iter != party.end(); ++iter){
            if(iter->allocation){
                double additional_seat = residual * iter->pr_vote_rate;
                double fraction = additional_seat - (int)additional_seat;
                iter->yeondong_seat = iter->tmp_yeondong_seat + (int)additional_seat;
                yeondong_seat_sum += iter->yeondong_seat;
                prior.insert(make_pair(fraction, iter - party.begin()));
            }
        }
        for(prior_iter = prior.begin(); prior_iter != prior.end(); ++prior_iter){
            if(yeondong_seat_sum == 30) break;
            ++party[prior_iter->second].yeondong_seat;
            ++yeondong_seat_sum;
        }
    }
    else{
        double reduction = 30.0 / yeondong_seat_sum;
        yeondong_seat_sum = 0;
        multimap<double, int, greater<double>> prior;
        multimap<double, int, greater<double>>::iterator prior_iter;
        for(iter = party.begin(); iter != party.end(); ++iter){
            if(iter->allocation){
                double decreased_seat = reduction * iter->tmp_yeondong_seat;
                double fraction = decreased_seat - (int)decreased_seat;
                iter->yeondong_seat = (int)decreased_seat;
                yeondong_seat_sum += iter->yeondong_seat;
                prior.insert(make_pair(fraction, iter - party.begin()));
            }
        }
        for(prior_iter = prior.begin(); prior_iter != prior.end(); ++prior_iter){
            if(yeondong_seat_sum == 30) break;
            ++party[prior_iter->second].yeondong_seat;
            ++yeondong_seat_sum;
        }
    }
}

void distribute_remains(){
    int seat_sum = 0;
    multimap<double, int, greater<double>> prior;
    multimap<double, int, greater<double>>::iterator prior_iter;
    for(iter = party.begin(); iter != party.end(); ++iter){
        if(iter->allocation){
            double seat = 17 * iter->pr_vote_rate;
            double fraction = seat - (int)seat;
            iter->yeondong_seat += (int)seat;
            seat_sum += (int)seat;
            prior.insert(make_pair(fraction, iter - party.begin()));
        }
    }
    for(prior_iter = prior.begin(); prior_iter != prior.end(); ++prior_iter){
        if(seat_sum == 17) break;
        ++party[prior_iter->second].yeondong_seat;
        ++seat_sum;
    }
}

bool comp(const Party& a, const Party& b){
    if(a.region_seat + a.yeondong_seat == b.region_seat + b.yeondong_seat)
        return a.name < b.name;
    else
        return a.region_seat + a.yeondong_seat > b.region_seat + b.yeondong_seat;
}

void print_answer(){
    sort(party.begin(), party.end(), comp);
    for(iter = party.begin(); iter != party.end(); ++iter){
        cout << iter->name << " " << iter->region_seat + iter->yeondong_seat << '\n';
    }
}

int main() {
    get_input();
    judge_allocation();
    calc_yeondong();
    distribute_remains();
    print_answer();
    return 0;
}

alinghi 3년 전 1

저도 30%에서 틀렸습니다. 떴는데

N-R 계산하는 과정에서

R을 잘못계산해서 틀렸습니다.

R을 계산할때 비례대표를 받는 당의 지역구만 빼서 계산해주어야 합니다.

tjwjdgus12 3년 전 1

와 감사합니다..... 거기였네요

N-R 계산 대신 "47 + 의석할당정당의 지역구 당선인 수 총합" 으로 하면 간단한데,

구현과정에 생각을 잘못해 의석할당정당이 아닌 정당의 지역구 당선인을 뺼셈했었네요ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 있을까요...ㅠㅠ

tjwjdgus12 4년 전 0

alinghi 3년 전 1

tjwjdgus12 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말