題目描述

A and B are playing a collaborative game that involves n stacks of coins, numbered from 1 to n. Every round of the game, they select a nonempty stack each, but they are not allowed to choose the same stack. They then remove a coin from both the two selected stacks and then the next round begins.

The players win the game if they manage to remove all the coins. Is it possible for them to win the game, and if it is, how should they play?

輸入描述:

The first line of input contains an integer n (2 ≤ n ≤ 50), the number of coin stacks. Then follows a line containing n nonnegative integers a1, a2, . . . , an, where ai is the number of coins in the i’th stack. The total number of coins is at most 1000.

輸出描述:

If the players can win the game, output a line containing “yes”, followed by a description of the moves. Otherwise output a line containing “no”. When describing the moves, output one move per line, each move being described by two distinct integers a and b (between 1 and n) indicating that the players remove a coin from stacks a and b. If there are several possible solutions, output any one of them.

示例1

輸入

3

1 4 3

輸出

yes
1 2
2 3
2 3
2 3

示例2

輸入

3
1 1 1

輸出

no

原題鏈接：https://ac.nowcoder.com/acm/contest/18456/C
來源：牛客網

原文翻譯

A和B正在玩一個合作游戲，游戲中涉及n個硬幣堆，編號從1到n，然后，他們從兩個選定的堆疊中取出一枚硬幣，然后開始下一輪游戲，

第一行輸入包含一個整數n（2≤n≤50），即硬幣堆的數量，然后是一行包含n個非負整數a1, a2, ... , an，其中ai是第i個硬幣堆中的硬幣數量，硬幣的總數最多為1000，

如果玩家能夠贏得比賽，則輸出包含 "是 "的一行，后面是對棋步的描述，否則就輸出包含 "否 "的一行，在描述動作時，每行輸出一個動作，每個動作由兩個不同的整數a和b（介于1和n之間）描述，表示玩家從堆疊a和b中取出一枚硬幣，

心路歷程

第一次解題：

第一次嘗試解題時想的比較簡單，首先既然一次拿倆個，拿硬幣數一定要先是偶數才成立；然后就是取硬幣的程序，起初認為只要用兩個指標分別指向兩個錢幣數不為0的洞上，讓其不相遇然后回圈取錢幣，直至錢幣取完，

這種思路通過48%的樣例，原因是操作思路太簡單，指標的運動是歷遍順序，缺乏機動性：

這里舉一個栗子：

1 2 3 4

0 1 3 4

0 0 2 4

0 0 1 3

0 0 0 3

按照原來的思想用倆指標找硬幣數不為0的兩個洞取出，會出現指標相遇而判no的情況，實際上該樣例可以通過，

第二次解題：

經過上一次的教訓，我認定兩指標的運動一定要滿足弄種規律

這時我結合了實際，將自己代入題中；假如我們現在在玩這樣一個游戲，想要一次在不同的洞里取出兩個硬幣，我們肯定不可能一根筋，哪有就找那，那樣太沒有大局觀，

正常的我們一定會有一個預判思想，去保證至少有兩個洞中硬幣數不為0，避免最后只剩一個洞有硬幣，而失敗的結局，

這時，我就有了想法，類似一種分蘋果的思想，要去保證每個人都感到合理，我們一般都會讓蘋果多的勻給少的，在本題中，最多和最少就是解題的關鍵所在，

舉個栗子：

對于這個樣例：1 1 6 8 9 11

我們為了去保證至少有兩個洞中硬幣數不為0；每次找一個最大最小值，讓其下標不同，這樣就保證了這一點；緊接著每次都從最大最小值對應的洞口取出該輪的兩枚硬幣，直至取完，便可完成程序，下面是該樣例的模擬操作步驟：

1 1 6 8 9 11
0 1 6 8 9 10
0 0 6 8 9 9
0 0 5 8 9 8
0 0 4 8 8 8
0 0 3 8 8 7
0 0 2 8 7 7
0 0 1 7 7 7
0 0 0 7 7 6
0 0 0 7 6 6
0 0 0 6 6 6
0 0 0 5 6 5
0 0 0 4 5 5
0 0 0 3 5 4
0 0 0 2 4 4
0 0 0 1 4 3
0 0 0 0 3 3
0 0 0 0 2 2
0 0 0 0 1 1
0 0 0 0 0 0

（這里要提示的一點是：當min=max時，要保證其對應的下標是不同的才能繼續）

代碼塊：

import java.io.*;

public class Main {
    static StreamTokenizer r;
    static PrintWriter pr;
    static BufferedReader re;
    static boolean isFlag = true;

    static {
        r = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        pr = new PrintWriter(new OutputStreamWriter(System.out));
        re = new BufferedReader(new InputStreamReader(System.in));
    }


    static int maxcursor;
    static int mincursor;
    static int Thecount;
    static int index = 0;

    static int cc[];/*記錄資料*/
    static int nec[];/*記錄答案*/

    public static void main(String[] args) throws IOException {
        int a = ini();
        cc = new int[a];

        for (int i = 0; i < cc.length; i++) {
            cc[i] = ini();
            Thecount += cc[i];
        }
        nec = new int[Thecount];

        if (Thecount % 2 == 0) {
            while (Thecount != 0) {
                 maxMin(cc);
                if (maxcursor == mincursor) {
                    isFlag = false;
                    break;
                }
               
                
            }
            if (isFlag) {
                System.out.println("yes");
                for (int i = 0; i < nec.length; i += 2) {
                    System.out.println((nec[i] + 1) + " " + (nec[i + 1] + 1));
                }
            } else {
                System.out.println("no");
            }

        } else {
            System.out.println("no");
        }


    }

    static int ini() throws IOException {
        r.nextToken();
        return (int) r.nval;
    }

    static void maxMin(int a[]) {//對于每個回合，我們都要找到陣列的最大最小值
        int b[] = a;
        int max = -1;
        int min = 1001;//注意點
        int index1 = -2;
        int index2 = -1;
        for (int i = 0; i < b.length; i++) {
            if (b[i] == 0) {
                continue;
            } else {
                if (b[i] < min) {
                    min = b[i];
                    index1 = i;
                }
                if (b[i] >= max) {
                    max = b[i];
                    index2 = i;
                }
            }
        }
        mincursor = index1;
        maxcursor = index2;

        nec[index] = mincursor;
        cc[mincursor]--;
        index++;

        nec[index] = maxcursor;
        cc[maxcursor]--;
        index++;

        Thecount -= 2;
    }

}

留在最后

這個題我想吐槽一點的時，“The total number of coins is at most 1000.”以及“The first line of input contains an integer n (2 ≤ n ≤ 50)”這兩段話讓我深感無語，

按理說n>=2,那么對于任意洞口，它的硬幣數不會超過999；但當我們把min設為1000時，在部分案例會出現：陣列越界的情況，

分析了下，可能情況就是某個樣例的硬幣數沒有小于1000的，導致在找最小值下標時未得到結果，mincursor直接等于了初始值-2；導致超出了陣列cc的下標范圍，

當我們把min的初始值改為1001時，問題得到了解決，