TIOJ 1210 圖論 之 簡單圖測試

Havel定理：對於一個簡單圖的等價條件


看到有人做到 XX ms，實在不知道QQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
typedef pair<int,int> pii;
int arr[10020];
int tmp[10020];
int main()
{
 int n;
 for(;;){
  scanf("%d", &n);
  if(n == 0) break;
  memset(arr, 0, sizeof(arr));
  int get_max = -1;
  int sum = 0;
  for(int lx = 0;lx < n;lx++){
   int inp;scanf("%d", &inp);
   arr[inp]++;
   get_max = max(get_max, inp);
   sum ^= inp&1;
  }
  if(sum&1 == 1){
   puts("No");
   continue;
  }
  bool ok = true;
  for(int lx = get_max;lx >= 0 and ok;){
   /*for(int ly = 0;ly <= get_max;ly++){
    printf("%d->%d ", ly, arr[ly]);
   }
   printf("\n");*/
   if(arr[lx] == 0){lx--; continue;}
   int pcnt = lx;
   arr[lx]--;
   for(int ly = lx;ly >= 1;ly--){
    if(arr[ly] >= pcnt){
     tmp[ly-1] = pcnt;
     arr[ly] -= pcnt;
     pcnt = 0;
    }else{
     tmp[ly-1] = arr[ly];
     pcnt -= arr[ly];
     arr[ly] = 0;
    }
   }
   for(int ly = lx-1;ly >= 0;ly--)
    arr[ly] += tmp[ly];
   if(pcnt > 0)
    ok = false;
  }
  if(arr[0] < 0) ok = false;
  puts(ok ? "Yes":"No");
 }
 return 0;
}