P10678 『STA - R6』月

P10678 『STA - R6』月 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

挺意外的一个题，从黄色到蓝色。

贪心思想比较好想，尽量把度数多的连在一起。这样会形成一个中心聚集的图，就可以使得最长直径尽量小。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m;

struct Node
{
    int x, id;
    
    bool operator<(const Node &W)const
    {
        return W.x < x;
    }
}g[N];

int main()
{
    int T;
    cin >> T;
    
    while (T -- )
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ )
        {
            int a, b;
            cin >> a;
            g[i] = {a, i};
        }
        sort(g + 1, g + 1 + n);
        
        int last = 2;
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= g[i].x; j ++ )
            {
                if (last > n) continue;
                printf("%d %d\n", g[last].id, g[i].id);
                g[last].x -- ;
                last ++ ;
            }
        }
    }
    
    return 0;
}