Codeforces Round #744 (Div. 3)-D. Productive Meeting

문제 설명

$n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다.

각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다.

한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다.

당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 위해서 어떤 사람들끼리 어떤 순서로 대화를 해야하는지 결정해야 한다.

Input
첫번째 줄은 테스트케이스의 수 $t (1 \le t \le 1000)$가 주어진다.

각 테스트 케이스의 첫번째 줄에는 회의에 참여하는 사람의 수 $n(2 \le n \le 2\cdot10^5)$ 가 주어진다.
두번째 줄에는 모든 사람의 사교성이 정수 $a_1, a_2, \dots, a_n(0 \le a_i \le 2 \cdots 10^5)$ 로 공백을 기준으로 주어진다.

Output
각 테스트 케이스마다 답을 출력한다.
답의 첫번째 줄에는 회의에서 가능한 최대의 대화 횟수 $k$를 출력한다.

뒤따르는 $k$개의 줄에는 누가 누구랑 대화를 나눴는지 경과 사항을 두 정수 $i$와 $j (1 \le i, j \le n, i \neq j)$를 통해서 출력한다.

Example
input
8
2
2 3
3
1 2 3
4
1 2 3 4
3
0 0 2
2
6 2
3
0 0 2
5
8 2 0 1 1
5
0 1 0 0 6

output
2
1 2
1 2
3
1 3
2 3
2 3
5
1 3
2 4
2 4
3 4
3 4
0
2
1 2
1 2
0
4
1 2
1 5
1 4
1 2
1
5 2

문제 접근

사용한 알고리즘: 그리디
걸린 시간 : 00:11
이 문제는 진짜 딱 보고 그리디로 풀면 되고, 무조건 사교성이 큰 사람끼리 대화를 붙이면 최대값을 구할 수 있겠다라고 생각을 해서 문제를 풀었는데, 계속 틀린 답이 나왔다. 결국 문제를 못풀고 virtual contest를 종료했는데, editorial을 보면서 왜 못풀었는지 곰곰히 생각을 해봤고 구현 능력이 부족하다는 것을 깨달았다. 문제를 풀 수 있다는 생각에 너무 급했고 침착하지 못한것 같았다. 좀 더 차근차근히 생각했으면 내가 생각한 것이 답이었는데, 너무 아쉬웠던 문제였다.

위에서 말했듯이 한 배열에 최대값을 가진 두 사람끼리 대화를 계속 진행하면 최대값이 나온다. 하지만 여기서 내가 놓친 것이 대화를 1회 진행하면 그 배열에서 최대값이 바뀔 수도 있다는 사실이었다. 만약 배열이 $[2, 3, 3, 4]$이면 3과 4가 대화를 진행했다. 그러면 배열은 $[2, 3, 2, 3]$이 된다. 내가 처음에는 계속 3과 4둘중에 한명이 0이 될때까지 계속 대화를 시켰고 이것이 문제였던 것이었다. 배열의 최대값은 대화를 1회 진행할때마다 바뀔 수 있으므로 배열이 $[2, 3, 2, 3]$이 되면 최대값인 2와 4가 대화를 해야한다.

즉 우리가 필요한 것은 계속 최대값을 빨리 구할 수 있으며, 최대값을 뽑아도 그 값이 없는 상태의 배열에서 최대값이 계속 유지되는 그런 자료구조이다. c++에서 이런 자료구조는 트리 형태로 구현된 set, map 그리고 priority_queue이다. 이중에서 나는 우선순위 큐를 선택했다. 왜냐하면 나머지 자료구조는 우리가 맨앞이나 맨 뒤가 최대값이라는 것을 보장할 수 없지만 c++의 우선순위 큐는 top()이 항상 그 배열의 최대값이기 때문에 최대값을 2개 꺼내야 하는 우리의 문제 풀이에 딱 맞았다. 이런 자료구조를 선택하는 능력도 구현과 문제해결능력에 필요한 것 같다.

이 문제는 0이 아닌 사교성을 가진 사람을 우선순위 큐에 넣고, 큐의 크기가 1이거나 0이 될때까지 반복을 시킨다. 우선순위 큐에서 최대값을 2개 꺼내고 두 사람끼리 대화를 시켜서 사교성을 1씩 떨어뜨린다. 이때 0이 되지 않으면 1씩 떨어뜨린 값을 다시 우선순위 큐에 넣는다. 아무리 원소를 넣어도 top()에는 그 배열의 최대값이 위치해있기 때문에 편하게 문제를 풀 수 있다.

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        priority_queue<pair<int, int>> pq;
        vector<pair<int, int>> ans;
        for(int i = 1; i <= n; i++){
            int num; cin >> num;
            if(num > 0) pq.emplace(num, i);
        }

        while(pq.size() > 1){
            auto a = pq.top();
            pq.pop();
            auto b = pq.top();
            pq.pop();

            ans.emplace_back(a.second, b.second);
            if(a.first > 1) pq.emplace(a.first - 1, a.second);
            if(b.first > 1) pq.emplace(b.first - 1, b.second);

        }

        cout << ans.size() << "\n";
        for(auto x : ans) cout << x.first << " " << x.second << "\n";
    }
    return 0;
}