pku1659 Frogs' Neighborhood

贪心
自己YY了一个贪心，AC了。。。
后来才知道，竟然还是个定理。。。“Havel-Hakimi定理”
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 struct A
 6 {
 7     int n, x;
 8 }a[12];
 9 
10 int map[12][12];
11 
12 int cmp(const void *a1, const void *b1)
13 {
14     return (*(struct A *)b1).x - (*(struct A *)a1).x;
15 }
16 
17 int main()
18 {
19     int t, n, i, j, sum, flag, cases;
20     scanf("%d", &t);
21     for(cases=1; t-- && scanf("%d", &n); cases++)
22     {
23         if(cases-1)
24         {
25             printf("\n");
26         }
27         sum = 0;
28         flag = 0;
29         memset(map, 0, sizeof(map));
30         for(i=1; i<=n; i++)
31         {
32             scanf("%d", &a[i].x);
33             a[i].n = i;
34             sum += a[i].x;
35         }
36         while(sum)
37         {
38             qsort(a+1, n, sizeof(a[0]), cmp);
39             flag = 0;
40             sum -= (a[1].x<<1);
41             for(i=2; i<=a[1].x+1; i++)
42             {
43                 map[a[1].n][a[i].n] = 1;
44                 map[a[i].n][a[1].n] = 1;
45                 a[i].x --;
46                 if(a[i].x < 0)
47                 {
48                     flag = 1;
49                     break;
50                 }
51             }
52             a[1].x = 0;
53             if(flag)
54             {
55                 break;
56             }
57         }
58         if(flag)
59         {
60             printf("NO\n");
61         }
62         else
63         {
64             printf("YES\n");
65             for(i=1; i<=n; i++)
66             {
67                 for(j=1; j<n; j++)
68                 {
69                     printf("%d ", map[i][j]);
70                 }
71                 printf("%d\n", map[i][j]);
72             }
73         }
74     }
75     return 0;
76 }