淵子賽馬 Time Limit: 1000 ms???Case Time Limit: 1000 ms???Memory Limit: 64 MB ? Description 賽馬是一古老的游戲，早在公元前四世紀的中國，處在諸侯割據的狀態，歷史上稱為“戰國時期”。在魏國作官的孫臏，因為受到同僚龐涓的迫害，被齊國使臣救出后，到達齊國國都。?
賽馬是當時最受齊國貴族歡迎的娛樂項目。上至國王，下到大臣，常常以賽馬取樂，并以重金賭輸贏。田忌多次與國王及其他大臣賭輸贏，屢賭屢輸。一天他賽馬又輸了，回家后悶悶不樂。孫臏安慰他說：“下次有機會帶我到馬場看看，也許我能幫你?！?
孫臏仔細觀察后發現，田忌的馬和其他人的馬相差并不遠，只是策略運用不當，以致失敗。?
比賽前田忌按照孫臏的主意，用上等馬鞍將下等馬裝飾起來，冒充上等馬，與齊王的上等馬比賽。第二場比賽，還是按照孫臏的安排，田忌用自己的上等馬與國王的中等馬比賽，在一片喝彩中，只見田忌的馬竟然沖到齊王的馬前面，贏了第二場。關鍵的第三場，田忌的中等馬和國王的下等馬比賽，田忌的馬又一次沖到國王的馬前面，結果二比一，田忌贏了國王。?
就是這么簡單，現在淵子也來賽一賽馬。假設每匹馬都有恒定的速度，所以速度大的馬一定比速度小的馬先到終點（沒有意外！！）。不允許出現平局。最后誰贏的場數多于一半(不包括一半)，誰就是贏家(可能沒有贏家)。淵子有N(1≤N≤1000)匹馬參加比賽。對手的馬的數量與淵子馬的數量一樣，并且知道所有的馬的速度。聰明的你來預測一下這場世紀之戰的結果，看看淵子能否贏得比賽。

?

Input 輸入有多組測試數據。?
每組測試數據包括3行：?
第一行輸入N(1≤N≤1000)。表示馬的數量。?
第二行有N個整型數字，即淵子的N匹馬的速度。?
第三行有N個整型數字，即對手的N匹馬的速度。?
當N為0時退出。

?

Output 若通過聰明的你精心安排，如果淵子能贏得比賽，那么輸出“YES”。?
否則輸出“NO”。

?

Sample Input

Original

Transformed

5 2 3 3 4 5 1 2 3 4 5 4 2 2 1 2 2 2 3 1 0

?

Sample Output

Original

Transformed

YES NO

?

Source 王曉淵 ——————————————————————分割線—————————————————————— 思路：此題為田忌賽馬，你所需要考慮的是N局M勝。其中M是N的一半多1或0.5。排序后把淵子的前M匹快馬跟國王的倒數M匹慢馬比較一下，全部勝出則淵子能贏。 代碼如下：（快速排序）

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b){return *(int *)b - *(int *)a; } int main(){int n, i;while(scanf("%d", &n) != EOF&&n){int flag = 0;int tian[n], king[n];for(i = 0; i < n; i++)scanf("%d", tian+i);for(i = 0; i < n; i++)scanf("%d", king+i);qsort(tian, n, sizeof(int), cmp);qsort(king, n, sizeof(int), cmp);if(n % 2 == 0){for(i = 0; i < n / 2 + 1; i++){if(tian[i] > king[n / 2 - 1 + i])flag++;}}else{for(i = 0; i < (n+1) / 2; i++){if(tian[i] > king[(n-1) / 2 + i])flag++;}}if(flag > n / 2)printf("YES\n");elseprintf("NO\n");}return 0; }
?

總結

以上是生活随笔為你收集整理的AOJ-AHU-OJ-5 渊子赛马的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。