sgu138:構(gòu)造
我太二了，想了一個排序貪心的算法，死活過不了test 8
后來看了別人的程序，才想到，原來可以從另一個方向思考。
可以知道一共會有 sum/2場比賽，
對于每一個人，可以讓他贏到只剩一場，然后輸?shù)糇詈笠粓觥?br>也就是根據(jù)題目中要求的輸出方法，選擇一場進(jìn)行第一列的填充，
剩下最后一個填到第二列。然后繼續(xù)選下一個
也就是按照如下方法進(jìn)行填充。
x_
x_
x_
x_
x_
x_
yx
y_
y_
y_
zy
z_
z_
然后空白的地方，隨便選一個沒用完的填上即可。
1
2 const int N = 128;
3 struct L{
4 int idx,val;
5 }a[N];
6 int n,sum,res[N*N][2];;
7 int cmp(L a,L b) { return a.val > b.val; }
8 void proc() //http://www.shnenglu.com/schindlerlee
9 {
10 int i,times = 0,j;
11 sort(a,a + n,cmp);
12 for (i = 0;i < n && times < sum;i++) {
13 while (a[i].val > 1 && times < sum) {
14 res[times++][0] = a[i].idx;
15 a[i].val--;
16 }
17 if(times < sum) {
18 res[times][1] = a[i].idx;
19 a[i].val--;
20 }
21 }
22
23 int top = 0;
24 while (a[top].val == 0) {
25 top++;
26 }
27 for (i = 0;i < sum;i++) {
28 printf("%d ",res[i][0]);
29 if (res[i][1]) {
30 printf("%d\n",res[i][1]);
31 }else {
32 printf("%d\n",a[top].idx);
33 a[top].val--;
34 if(a[top].val == 0) {top++;}
35 }
36 }
37 }
38 int main()
39 {
40 int i,j,k;
41 scanf("%d",&n);
42 for (i = 0;i < n;i++) {
43 scanf("%d",&a[i].val);
44 a[i].idx = i + 1;
45 sum += a[i].val;
46 }
47 sum /= 2;
48 printf("%d\n",sum);
49 proc();
50 return 0;
51 }
52