글 읽기 - 반례를 못 찾겠습니다

rshtiger 3년 전 0

이 문제는 게시판에도 질문글이 잘 없어 혼자 최대한 머리를 굴려 보았는데

50%에서 계속 틀리네요 ㅠㅠ

간단하게 설명하자면

가장 적은 사람이 원하는 책을 먼저 골라주고

해당 책을 리스트에서 지웁니다

그 다음 책을 받은 사람이 원했던 책들에 대해 원하는 사람 수를 1만큼 줄여 줍니다.

줄 수 있는 책이 없어지면(+남은 책들을 원하는 사람이 아무도 없으면) 루프를 끝냅니다.

혹시 어떤 반례가 있을까요..?

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    int T, a, b;
    cin >> T;
    while(T--){
        int N, M, ans = 0;
        cin >> N >> M;
        set<int> book[1010];
        vector<int> stu[1010];

        for(int i = 0; i < M; i++){
            cin >> a >> b;
            for(int j = a; j <= b; j++){
               book[j].insert(i);
               stu[i].emplace_back(j);
            }
        

        while(1){
            int minIdx, minSize = 99999;
            for(int i = 1; i <= N; i++){
                if(book[i].size() && (book[i].size() < minSize)){
                    minIdx = i;
                    minSize = book[i].size();
                }
            }
            if(minSize == 99999) break;

            int stuNum = *book[minIdx].begin();
            for(int n : stu[stuNum])
                book[n].erase(stuNum);
            stu[stuNum].clear();
            book[minIdx].clear();
            ++ans;
        }

        cout << ans << "\n";
    }


}

yj10516 3년 전 1

그대로 복사 붙여넣기를 했는데 {} 괄호가 맞지 않아서, 21번째 줄에 괄호 닫으셨다고 가정했습니다.

﻿1
﻿5 5
﻿2 5
﻿2 5
 2 5
 1 2
 1 1
 ================
 Answer: 5
 Output: 4

yj10516 3년 전 1

복사 붙여넣기가 안되네요

5 5

2 5

1 2

1 1

rshtiger 3년 전 0

아... 원하는 사람이 가장 적은 책을 먼저 분배했는데

누구한테 분배하는지를 안 넣었네요... 아직 갈 길이 먼 것 같습니다 ㅠㅠ

감사합니다!!

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다

rshtiger 3년 전 0

yj10516 3년 전 1

yj10516 3년 전 1

rshtiger 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말