cf[educational55]D

发表于 | 阅读数 次

链接:cf[educational55]D

题解

  • 首先，如果总度数小于2*n-2的话无解。
  • 对于度数大于1的点，把他们顺序链接
  • 对于度数等于1的点，把他们和度数大于1的点连起来即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6+7;
template <typename T>inline void read(T &x){
	char c;int sign=1;x=0;
	do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
	do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
	x*=sign;
}
int n,s,k=1,lst,num,a[N];
int main(){
	read(n);
	rep(i,1,n){read(a[i]);s+=a[i];num+=a[i]==1;}
	if(s<2*n-2)return 0*puts("NO");
	printf("YES %d\n%d\n",min(n-num+1,n-1),n-1);
	rep(i,1,n)if(a[i]>1){
		if(lst)printf("%d %d\n",lst,i);
		else a[i]++;
		lst=i;
	}
	rep(i,1,n)if(a[i]==1){
		if(lst){
			printf("%d %d\n",i,lst);
			lst=0;continue;
		}
		while(a[k]<=2&&k<=n)++k;
		a[k]--;
		printf("%d %d\n",i,k);
	}
	return 0;
}