a312:
P-4-2. 笑傲江湖之三戰
內容
笑傲江湖的遊戲中，你扮演令狐沖的角色，因為「長恨此身非我有，何時忘卻盈盈」，所以你率領任我行等魔教高手前往少林寺搭救任盈盈，欲知故事原委可參見笑傲江湖第27回「三戰」。套句丸尾班長的口頭禪，總而言之，少林寺與五嶽劍派等正教派出n位高手，而你方也有n位高手，每個人都有一個戰力值。雙方要進行一對一的對戰，每個人不管輸或贏都只能比一場，假設兩人對戰時，戰力值高的獲勝。對於對方的每一位高手，你可以指定派哪一位與其對戰，為了解救盈盈，你希望贏越多場越好，平手則沒有幫助。請計算出最多能贏多少場。
輸入說明
第一行是一個正整數n，第二行有n個非負整數是對方的戰力，第三行有n個非負整數是我方的戰力，同行數字間以空白間格。n與戰力值不超過1e5。
輸出說明
輸出最多可能的勝場數。
範例輸入
#1
5 3 1 7 0 2 8 3 5 0 0
範例輸出
#1
3
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 ：
我們只要關心可以戰勝的那些場次需要誰去出戰，其他場次贏不了，就在剩下的人裡面隨便挑選去應戰。假設我方目前最弱的戰力是a而對方最弱的是b，
如果a <= b，則a對誰都不會贏，是沒用的，可以忽略。否則a > b，我們宣稱「一定有一個最佳解是派a去出戰b」，證明如下：
假設在一個最佳解中，a對戰x而y對戰b，我們將其交換改成「a對b而y對x」。根據我們的假設y>= a，交換後a可以贏b而y對x的戰績不會比a對x差，所以交換後勝場數不會變少。
既然如此，我們可以確定派a對戰b一定可以得到最佳解，並將a與b移除後，繼續依照上述原則挑選。
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||