OpenJudge Tian Ji -- The Horse Racing

目錄

Tian Ji -- The Horse Racing

要求：

描述：

輸入 ：

輸出： 

樣例輸入： 

樣例輸出：

問題分析：

情況一：

情況二：

情況三：

最終代碼：

總結：

其他思路：

Tian Ji -- The Horse Racing

要求：

總時間限制: 5000ms

記憶體限制: 65536kB

描述：

Here is a famous story in Chinese history. 

That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others. 

Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser. 

Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian. 

Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match. 

It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China? 

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching... 

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses -- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem. 

In this problem, you are asked to write a program to solve this special case of matching problem.

輸入 ：

The input consists of up to 50 test cases. Each case starts with a positive integer n ( n<=1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian's horses. Then the next n integers on the third line are the speeds of the king's horses. The input ends with a line that has a single `0' after the last test case.

輸出： 

For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.

樣例輸入： 

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
           

樣例輸出：

200
0
0
           

問題分析：

這是衆所周知的田忌賽馬問題，我們先來理一下這個英文題面。田忌和齊王賽馬，約定誰赢一局 就會從對手那裡赢取200銀元. 如果雙方平局，則錢數不會發生變化。那麼對于給定的馬速序列，我們希望知道田忌最多能夠赢多少銀元，或者說最少會輸掉多少銀元。

輸入有若幹組，以0結束；每一組中第一行n代表雙方各有多少匹馬，接下來的兩行分别代表田忌的馬的速度與齊王的馬的速度，（注意：雖然樣例是從大到小給出，但測試時資料并不一定按照從大到小給出）最後輸出田忌所赢錢數就可以了。

while(scanf("%d",&n)&&n!=0){
        //輸入部分
        cin.get();//因為用的是scarf，是以需要讀掉每行最後的回車
        int Tian[n];
        int King[n];
        for(int i=0;i<n;i++){
            scanf("%d",&Tian[i]);
        }
        cin.get();
        for(int i=0;i<n;i++){
            scanf("%d",&King[i]);
        }
        cin.get();
}
           

一個自然的思路是通過搜尋（枚舉），周遊所有可能，進而找到收益最大的值。但我們注意到雙方的馬匹數是0～1000，這個資料還是非常大的，因為周遊所有可能的時間複雜度是O(n!)，也就是最多需要進行1000!次枚舉，這個時間是我們不能忍受的，即使本題時間要求是5000ms。

是以我們希望找到一些好的算法（貪心），結合曆史上的田忌賽馬事件，我們可以簡單地得出一個粗糙的“結論”：如果我們用自己的劣馬耗掉對方的良馬，我方的優勢就會擴大。那麼基于這樣一個“結論”，我們可以對這個想法進行精細化讨論和實作。

首先我們需要對雙方的馬進行排序，以便我們後續查找對應的馬。（這裡用到了lambda表達式進行從大到小排序，如果不清楚的話，自己寫一個比較函數或者預設從小到大排序也可以）

sort(King,King+n,[](int a,int b){return a>b;});//對于傳入的int型a和b,傳回a>b的bool值
sort(Tian,Tian+n,[](int a,int b){return a>b;});
           

情況一：

是以我們就來考慮田忌方最差的馬，我們希望可以最大化利用這匹馬，那麼當我們這匹馬連對面最差的馬都不如的話，直接用它來消耗對面最好的馬。（這匹馬不管面對誰，結果都為負，是以消耗掉對面最好的馬就是收益最好的結果） 

田忌賽馬曆史故事告訴我們的隻有以上規則，但我們可以看到這個規則很不完善：我們仍需分類讨論，當我們的最劣馬等于對方最劣馬時以及優于對方最劣馬的情況。

情況二：

如果我方的最劣馬優于對方的最劣馬，若此時我們仍用此馬來消耗對面最優馬，這個情況是不好的，因為我們總能找到一個至少不差并且可能更優的局面：

假設我們現在不考慮己方最差馬N和對方最優馬P後得到的最大收益是K，那麼用最差馬消耗對面最優馬的最佳收益就是(K+(N與P比賽結果))*200，那麼在該局面下，我方總有一匹馬M和對方最差馬Q比賽并且獲勝(M>=N>Q)，那麼當我們用N來和Q比，用M來跟P比，其他比賽不變，我們此時的收益為((K-1)+1+(M與P比賽結果))*200，由于M>=N，是以這個結果至少不會差于上一個局面。

是以如果我方的最劣馬優于對方的最劣馬，我們總是用己方最劣馬來和對方最劣馬比賽并獲勝。

情況三：

如果我方的最劣馬剛好和對方最劣馬相當時，我們怎麼處理？

考慮這兩組資料：

2
20 10
15 10
2
15 10
20 10
           

對于第一組，我們不能用己方最差換對面最好，這樣做（一輸一勝）的收益是0，小于最大收益（一平一勝）200；但是對于第二組，我們必須用己方最差換對面最好，（一輸一勝）收益為0，大于（一平一輸）收益為-200.

是以從上述的例子中我們可以發現此時需要針對最優馬再進行分類讨論，如果我方最優馬比對方更好，直接最優馬先赢下這一局，否則就用最劣馬去換掉對面最優的。（證明方式類似上面）

最終代碼：

是以在上面的分類讨論中，我們已經把情況讨論齊全。

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)&&n!=0){
        //輸入部分
        cin.get();
        int *Tian=new int[n];//田忌
        int *King=new int[n];//齊王
        for(int i=0;i<n;i++){
            scanf("%d",&Tian[i]);
        }
        cin.get();sort(Tian,Tian+n,[](int a,int b){return a>b;});
        for(int i=0;i<n;i++){
            scanf("%d",&King[i]);
        }
        cin.get();sort(King,King+n,[](int a,int b){return a>b;});
        //算法部分
        int Money=0;int KingLast=n-1;int KingFirst=0;int TianFirst=0;
        for(int TianLast=n-1;TianLast>=TianFirst;){
            if(Tian[TianLast]<King[KingLast]){//情況一
                Money--;
                KingFirst++;
                TianLast--;
            }
            else if(Tian[TianLast]>King[KingLast]){//情況二
                KingLast--;
                Money++;
                TianLast--;
            }
            else{//情況三
                if(Tian[TianFirst]<=King[KingFirst]){//如果最優沒有對面好，用最後去換
                    if(Tian[TianLast]<King[KingFirst]) Money--;
                    KingFirst++;
                    TianLast--;
                }
                else{//如果己方最優馬比對方最優馬好
                    Money++;
                    KingFirst++;
                    TianFirst++;
                }
            }
        }
        printf("%d\n",Money*200);
        //釋放記憶體
        delete []Tian;
        delete []King;
    }
}
           

總結：

 一道經典的貪心算法，最難的就是對各種情況的讨論以及證明，一定切記避免想當然，不然很容易漏掉一些情況。希望這篇文章對您有所幫助。最後求贊求關注😂（對于貪心題目，時空間複雜度不重要，重要的是自己算法的完備性和合理性）

其他思路：

其實不一定需要先考慮最劣馬的分類情況，也可以反過來先考慮最優馬，但是我覺得沒有最劣馬讨論直覺，故在此沒有列出。