Degree Set CodeForces - 976D（双指针）

题意：

　　构造一个无向图，使得无向图里的所有点的度数 所组成的集合 即为给出的几个数

解析：

　　题中的数是以上升的顺序给出的，

　　我们对于d+1个数进行处理，对于当前数i，有两个操作

　　1、向后边的所有点连边 称为主动连边

　　2、跳过该数 即不向后边的点连边，称为被动连边

　　设tot = d+1， l = 1， r = n，ready 为对于当前点i前面的主动连边的点的数量

　如果ready + tot - i == d[r] （即前面的点向它连的边 加上 当前点向后边的点连的边（即为总点数减去当前点的下标（下标从1开始））等于d[r]）

　　那就ready++，即把当前点和后边的点连边

　如果ready == d[l] 说明当前点前面的点 向后连的边 等于d[l]   即当前点不向后边主动连边

　　　那就l++， r--；  //因为如果要符合这个判断  肯定符合上一个判断 因为只有符合上一个判断的时候ready才会++ 才会加到

#include <bits/stdc++.h>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = 1e6+, INF = 0x7fffffff;

typedef long long LL;

int n;

int d[maxn];

vector<int> G[maxn];

int tot;

void build(int u)

{

    for(int i=u+; i<=tot; i++)

        G[u].push_back(i);

}

int main()

{

    cin>> n;

    for(int i=; i<=n; i++)

    {

        cin>> d[i];

    }

    tot = d[n] + ;

    int l = , r = n, ready = ;

    LL ans = ;

    for(int i=; i<=tot; i++)

    {

        if(ready == d[l])

            l++, r--;

        else if(ready + tot - i == d[r])

            ready++, build(i), ans += tot - i;  //同时ans 记录一共有几条边

    }

    cout<< ans <<endl;

    for(int i=; i<=tot; i++)

        for(int j=; j<G[i].size(); j++)

            cout << i << " " << G[i][j] <<endl;

    return ;

}