UESTC_握手 CDOJ 913

时间：2022-01-13 07:20:27

握手

Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

一群人参加了一次聚会，其中有一些人是好朋友。一对朋友见面后握手且仅握一次手，并且每个人不会和自己握手（废话！）。现在告诉你每个人一共握了几次手，请你判断是否存在一种朋友关系满足每个人的握手数。

Input

输入多组数据，第一行一个数T，表述数据组数。每组数据第一行输入一个数n，表示有n个人参加了聚会，下一行有n个数，di到dn ，di表示第i个人的握手数。 （1≤n≤105 ，输入的所有d之和不超过5×105）

Output

存在这种朋友关系输出YES，反之NO。

Sample input and output

Sample Input Sample Output 
3

3

0 1 1

3

2 2 2

3

1 1 1
 
YES

YES

NO

Source

2014 UESTC Training for Graph Theory
解题报告：
 即判断是否可图利用Havel-Hakimi定理即可,具体可百度...
 因为p的和不超过5 * 1e5 ,直接暴力模拟即可
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <set>

#include <vector>

using namespace std;

const int maxn = 1e5 + ;

int d[maxn];

multiset<int,greater<int> >s;

vector<int>temp;

int main(int argc,char *argv[])

{

  int Case;

  scanf("%d",&Case);

  while(Case--)

   {

         int n;

         scanf("%d",&n);

         s.clear();

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

          {

             int u;

          scanf("%d",&u);

          s.insert(u);

       }

      int ans = ;

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

       {

            set<int>::iterator it = s.begin();

            if (*it >= s.size() || *it < )

             {

                ans = ;

             break;

          }

         int tot = *it;

         temp.clear();

         s.erase(it);

         while(tot)

          {

               it = s.begin();

               temp.push_back((*it)-);

               tot--;

               s.erase(it);

          }

         for(int j =  ; j < temp.size() ; ++ j)

          s.insert(temp[j]);

       }

      if (ans)

       printf("YES\n");

      else

       printf("NO\n");

   }

  return ;

}

相关文章