CodeForces-1082D Maximum Diameter Graph

题目链接：CodeForces-1082D Maximum Diameter Graph

题意

有n个点，第i个点最大的度为$a_i$，求令图连通后直径最大的构图方案。

---

思路

判断是否能构造一个连通图，如果可以的话，将所有度数大于1的点连成一条线，剩下度为一点尽量连一下最左边和最右边的点，然后随便连即可，这样贪心一定是最优的。

---

 实现代码

#include <cstdio>
const int maxn = 510;
struct Node
{
    int deg, idx;
} no[maxn];
struct Edge
{
    int u, v;
} ed[maxn];
int no1[maxn];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int cnt = 0, cnt1 = 0, tot = 0, sum = 0, ai;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &ai);
            sum += ai;
            if (ai > 1) no[cnt++] = {ai, i};
            else no1[cnt1++] = i;
        }
        if (sum < (n - 1) * 2) {
            puts("NO");
            continue;
        }
        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < cnt - 1; i++) {
            ed[ans2++] = {no[i].idx, no[i+1].idx};
            no[i].deg--, no[i+1].deg--;
            ans1++;
        }
        if (cnt1) {
            ed[ans2++] = {no1[cnt1-1], no[0].idx};
            no[0].deg--;
            ans1++;
            cnt1--;
        }
        if (cnt1) {
            ed[ans2++] = {no1[cnt1-1], no[cnt-1].idx};
            no[cnt-1].deg--;
            ans1++;
            cnt1--;
        }
        while (cnt1) {
            for (int i = 0; i < cnt; i++) {
                if (no[i].deg) {
                    ed[ans2++] = {no[i].idx, no1[cnt1-1]};
                    no[i].deg--;
                    cnt1--;
                }
                if (cnt1 == 0) break;
            }
        }
        printf("YES %d
", ans1);
        printf("%d
", ans2);
        for (int i = 0; i < ans2; i++) printf("%d %d
", ed[i].u, ed[i].v);
    }
    return 0;
}