首页 > 代码库 > Traveling

Traveling

题目描述

SH likes traveling around the world. When he arrives at a city, he will ask the staff about the number of cities that connected with this city directly. After traveling around a mainland, SH will collate data and judge whether the data is correct.

 A group of data is correct when it can constitute an undirected graph.

输入

There are multiple test cases. The first line of each test case is a positive integer N (1<=N<=10000) standing for the number of cities in a mainland. The second line has N positive integers a1, a2, ...,an. ai stands for the number of cities that connected directly with the ith city. Input will be ended by the END OF FILE.

输出

If a group of data is correct, output "YES" in one line, otherwise, output "NO".

样例输入

8
 7 7 4 3 3 3 2 1 
10 
5 4 3 3 2 2 2 1 1 1 

样例输出

NO 
YES
 1 /***********************************************************
 2  * OS       : Win7
 3  * Complier : GCC(G++)
 4  * All Rights Reserved by GingerZeng.
 5  **********************************************************/
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<algorithm>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<iostream>
12 using namespace std;
13 typedef long long LL;
14 const int inf=1e6+10;
15 int a[inf];
16 LL s[inf];
17 int cmp(int a,int b)
18 {
19   return a>b;
20 }
21 int main()
22 {
23     int n;
24     while(~scanf("%d",&n))
25     {
26         LL sum=0;
27         for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
28         sort(a+1,a+1+n,cmp);
29         for(int i=1;i<=n;i++){sum+=a[i];s[i]=sum;}
30         if(sum%2==0)
31         {
32             int flag=0;
33             for(int k=1;k<=n;k++)
34             {
35                 LL all=0;
36                 LL ans=0;
37                 if(k<n)
38                 {
39                     if(k>a[k+1])
40                     ans=s[n]-s[k];
41                     else
42                     {
43                         int l=k;int r=n;int mid;
44                         while(r-l>1)
45                         {
46                             mid=(l+r)/2;
47                             if(a[mid]>=k)l=mid;
48                             else r=mid;
49 
50                         }
51                         ans=s[n]-s[r-1]+(r-1-k)*k;
52                     }
53                 }
54              all+=ans;
55              LL temp=all+k*(k-1);
56              if(s[k]>temp){cout<<"NO"<<endl;flag=1;break;}
57             }
58             if(!flag)cout<<"YES"<<endl;
59         }
60         else
61         {
62             cout<<"NO"<<endl;
63         }
64 
65     }
66     return 0;
67 }