a995: 田忌賽馬
標籤 : STL greedy
通過比率 : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-07-15 16:38

內容

齊使者梁,孫臏以刑徒陰見,齊使。齊使以為奇,竊載與之齊。齊田忌客待之。忌與齊諸公子馳逐重射。孫臏見其馬足不甚相遠,馬有上、中、下輩。於是孫臏謂田忌曰:「君重射,臣能令君勝。」田忌信然之,與王及諸公子逐射千金。及臨質,孫臏曰:「今以君之下駟彼上駟,取君上駟與彼中駟,取君中駟與彼下駟。」既馳三輩畢,而田忌一不勝而再勝,卒得五千金。於是忌孫臏於威王。威王問兵法,遂以為師。 

《史記》卷六十五:《孫子吳起列傳第五》

 

注釋:

1. 如:前往,到...去

2. 以刑徒:以刑徒的身份。刑徒:受過刑的人

3. 陰:秘密地

4. 說:遊說,與「睡」同音

5. 以為奇:以為此人是難得的人才,此句賓語省略

6. 與之齊:與孫臏前往齊國,此處賓語省略。之:動詞,前往

7. 將:將軍

8. 善:賞識

9. 客待之:把孫臏當作賓客來對待。之:代詞,指前面提及的主角孫臏

10. 數,與「碩」同音,數次、屢次

11. 馳逐重射:賽馬賭博。馳逐,賽馬。重射,押重金賭輸贏。

12. 馬足:馬的腳力

13. 第:通「弟」,但、儘管。

14. 信然之:相信並答應孫臏。之:代詞,指孫臏

15. 臨質:比賽快要開始時。質:對抗,此處引伸為比賽

16. 與:對付

17. 再勝:贏了兩場

18. 進:舉薦

19. 以為師:以孫臏為老師,此句省略賓語

 

看完之後,應該就知道這一題要問什麼了吧!

輸入說明

多個測資點,每個測資點單筆測資

測資中第一行是一正整數 $T$,代表接下來有 $T$ 場比賽

接下來對於每一場比賽

第一行是一個正整數 $N$

代表這一場比賽中共有幾隻馬要跑

再接下來的兩行分別是自己和對手的所有馬匹

第一行有 $N$ 個正整數,代表是自己的所有馬匹,而數字是他的戰力 (跑速)

而第二行亦相同

 

定義贏的條件是:自己的勝場「大於」對方的勝場 (馬平局、人平局皆不算贏)

我們已知對方派出馬的順序

請問能不能贏過他?

 

提示:線索就是古人的大智慧

輸出說明

若可以贏,輸出 "YES" (不含引號),反之輸出 "NO" (不含引號)

每一個輸出之間以換行分隔

範例輸入
2
5
5 8 9 4 6
2 5 7 1 2
4
1 2 4 9
5 4 3 8
範例輸出
YES
NO
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 0.5s , <1M
公開 測資點#1 (10%): 0.5s , <1M
公開 測資點#2 (10%): 0.5s , <1M
公開 測資點#3 (10%): 0.5s , <1M
公開 測資點#4 (10%): 0.5s , <10M
公開 測資點#5 (50%): 0.5s , <10M
提示 :

對於所有測資:$1 \leq N \leq 10^5$,$1 \leq$ 戰力 $\leq 10^5$,$T \leq 100$

測資 $\text #00$:$1 \leq N \leq 30$,$1 \leq$ 戰力 $\leq 1000$,保證兩方的馬戰力都不同,且己方沒有戰力相同的馬,$T = 100$

測資 $\text #01$:$1 \leq N \leq 30$,$1 \leq$ 戰力 $\leq 1000$,保證己方沒有戰力相同的馬,$T = 100$

測資 $\text #02$:$1 \leq N \leq 1000$,保證兩方的馬戰力都不同,保證己方沒有戰力相同的馬,$T = 100$

測資 $\text #03$:$1 \leq N \leq 1000$,保證己方沒有戰力相同的馬,$T = 100$

測資 $\text #04$:保證己方沒有戰力相同的馬,$T = 10$

測資 $\text #05$:無特別限制,$T = 10$

 

 

$2024/7/15\ 04:38$ 已修改時限並 $rejudge$

標籤:
STL greedy
出處:
[管理者:
frankie (34104)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」