The tunnels of Cu Chi are an immense network of underground tunnels connecting rooms located in the Cu Chi District of Ho Chi Minh City. The Cu Chi tunnels were the location of several military campaigns in the 1960s. Nowadays, it is a popular tourist destination.
There are documents from trusted sources about a private network of tunnels in this area used by a secret forces unit but it has not been discovered. According to the documents, this private network has N rooms (numbered from 1 to N) connected by N−1 bidirectional tunnels. Room 1 is the entry point from the ground surface to this underground network. From room 1, you can follow the tunnels to go to any of the rooms. The rooms are numbered in such a way that, if you follow the shortest path from room 1 to any room X, the sequence of visited rooms’ indices will be increasing. The image below shows a valid map of this network.
\includegraphics[width=0.5\textwidth ]{example1.png}
The network below is invalid, since the path from 1 to 4 is 1 - 3 - 2 - 4, which is not increasing:
\includegraphics[width=0.5\textwidth ]{example2.png}
There is also an old article from an unknown source mentioning about Di which is the number of rooms directly connected to room i.
Given an array D of size N, your task is to verify if it is possible to have such a network.
Input
The first line contains an integer N - the number of rooms in the network (2≤N≤1000).
The second line consists of N integers Di - the number of rooms that are directly connected to room i (1≤Di≤N−1).
Output
Print YES/NO if it is possible/impossible to have such a network, respectively.
Sample Input 1 Sample Output 1
8
3 2 2 1 1 3 1 1
YES
Sample Input 2 Sample Output 2
4
3 3 3 3
NO
给定节点的度数，求是否存在节点递增的树存在
模拟即可；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 2000005
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
ll quickpow(ll a, ll b) {
ll ans = 1;
while (b > 0) {
if (b % 2)ans = ans * a%mod;
b = b / 2;
a = a * a%mod;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
ll ves[maxn];
void revs() {
for (ll i = 1; i <= 1000000; i++) {
ves[i] = quickpow(i, mod - 2);
}
}
//ull Mod = quickpow(2ull, 47ull);
int a[maxn];
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
int i;
int tot = 0;
for (i = 1; i <= n; i++) {
cin >> a[i];
tot += a[i];
}
int cnt = 0;
int flag = 0;
if (tot % 2 == 0 && tot / 2 == n - 1) {
for (i = n; i >= 1; i--) {
if (i == 1) {
cnt -= a[i];
}
else if (a[i] != 1 && i != 1) {
if (cnt < a[i] - 1) {
flag = 1;
break;
}
cnt -= a[i] - 2;
}
else cnt++;
}
if (flag == 1 || cnt < 0)cout << "NO" << endl;
else cout << "YES" << endl;
}
else cout << "NO" << endl;
return 0;
}