coders 문제에 생각하지 못한 예외가 있나봐요

  • yangjy0113
    yangjy0113

    제가 생각한 알고리즘을 간단히 적어보면

    1. A의 내림차순, B의 내림차순으로 정렬

    2. A,B를 0~100까지 전부탐색 (총 10000 loop)

    3. 원하는 후보와 득표수가 같은 아이들은 제외하고 나머지에 대해 탐색

    4. A, B에 대해 C를 정하고 원하는 후보가 들어가지 못하도록 만드는데 필요한 일본득표수를 정한다.

    5. 2에서 구한 일본득표수의 총합이 주어진 K보다 작거나 같은경우가 있다면 원하는 후보가 못올라갈 수 있으므로 1로 가서 계속 반복

    예외사항을 다 고려한 것 같은데 계속 오답이 나오네요.
    고려하지 못한게 뭐가 있을까요?

    아래는 코드입니다.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional>
    using namespace std;
    
    int M, N, K;
    int KOR, CHI;
    vector<pair<int, int>> cand;
    
    void input() {
        cin >> M >> N >> K;
        cand = vector<pair<int, int>>(M);
        for (int i = 0; i < M; ++i) {
            cin >> cand[i].first >> cand[i].second;
        }
    }
    
    vector<int> calcB(int A, int idx) {
        vector<int> b;
        for (int i = idx; i < M; ++i) {
            b.push_back(cand[i].first * A + cand[i].second * (100 - A));
        }
        return b;
    }
    
    int selectC(int A, int B, int i) {
        // KOR * A > cand[i].first * A + K * (100 - A)
        int C = 100 - A - B;
        if (C == 0)
            return 1e9;
        int res = (KOR * A + CHI * B + 1 - cand[i].first * A - cand[i].second * B + C - 1) / C;
        //cout << "K: " << res << " " << endl;
        return res;
    }
    
    bool isPossible(int A) {
        int k = 0;
        int idx = 0;
        while (idx < cand.size() && KOR == cand[idx].first) idx++;
        if (idx + N > cand.size()) {
            return true;
        }
    
        for (int B = 0; B <= (100 - A); ++B) {
            k = 0;
            vector<bool> selectedB(M, false);
    
            for (int i = idx; i < M; ++i) {
                if (cand[i].first * A + cand[i].second * B > KOR * A + CHI * B) {
                    selectedB[i] = true;
                    k++;
                }
            }
            int numC = 0;
            for (int i = idx; k < N && i < M; ++i) {
                if (selectedB[i]) continue;
                k++;
                numC += selectC(A, B, i);
            }
            if (k < N || numC <= K) return false;
        }
        return true;
    }
    
    void solve() {
        sort(cand.begin(), cand.end(), greater<pair<int, int>>());
        for (int i = 0; i < cand.size(); ++i) {
            cout << cand[i].first << " " << cand[i].second << endl;
        }
        KOR = cand[0].first;
        CHI = cand[0].second;
    
        for (int A = 0; A < 100; ++A) {
            if (isPossible(A)) {
                cout << A << endl;
                return;
            }
        }
        cout << "100" << endl;
    }
    
    int main() {
        int T;
        cin >> T;
        while (T--) {
            input();
            solve();
        }
    }
    

    8년 전
1개의 댓글이 있습니다.
  • yangjy0113
    yangjy0113

    지우고 다시 짰더니 풀렸습니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.