g310: pD. 甜甜圈大對決(Donut)
Tags : Greedy
Accepted rate : 76人/94人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-16 16:39

Content

現在有兩家甜甜圈店 x 和 y,由左至右各有 N 個甜甜圈,

即 x0, x1, ..., xN-1 和 y0, y1, ..., yN-1

甜甜圈 xi 會和甜甜圈 yi 做比較,

當 xi > yi 時,視為 xi 獲勝;

當 xi < yi 時,視為 yi 獲勝;

當 xi = yi 時,則視為平手。

 

現在已知甜甜圈店 x 會將其所有甜甜圈,依照分數大小,由小至大以 x0, x1, ..., xN-1 出戰

在此條件下,已知 y 所有可以派出的甜甜圈數值,

若 y 以最佳策略出戰,請問最多可在 N 場比賽中獲勝幾場?

Input

第一行有一個正整數 N

代表共有 N 場的比賽 ( 1 ≤ N ≤ 1,000,000 )

 

第二行有 N 個正整數 x ( 1 ≤ x ≤ 1,000,000 )

由左至右,依序代表甜甜圈店 x 「將會」派出的甜甜圈值

並且這 N 個值必定由小至大

 

第三行有 N 個正整數 y ( 1 ≤ y ≤ 1,000,000 )

由左至右,依序代表甜甜圈店 y 「可以」派出的甜甜圈值,

為方便計算,這 N 個值將由小至大給予

 

Output

 y 以最佳策略出戰,最多可在 N 場比賽中獲勝幾場

Sample Input #1
3
60 80 100
50 70 90
Sample Output #1
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 0.8s , <1K
公開 測資點#1 (5%): 0.8s , <1K
公開 測資點#2 (5%): 0.8s , <1K
公開 測資點#3 (5%): 0.8s , <1K
公開 測資點#4 (5%): 0.8s , <1K
公開 測資點#5 (5%): 0.8s , <1M
公開 測資點#6 (5%): 0.8s , <1M
公開 測資點#7 (5%): 0.8s , <1M
公開 測資點#8 (5%): 0.8s , <1M
公開 測資點#9 (5%): 0.8s , <1M
公開 測資點#10 (5%): 0.8s , <10M
公開 測資點#11 (5%): 0.8s , <10M
公開 測資點#12 (5%): 0.8s , <10M
公開 測資點#13 (5%): 0.8s , <10M
公開 測資點#14 (5%): 0.8s , <10M
公開 測資點#15 (5%): 0.8s , <1M
公開 測資點#16 (5%): 0.8s , <50M
公開 測資點#17 (5%): 0.8s , <10M
公開 測資點#18 (5%): 0.8s , <50M
公開 測資點#19 (5%): 0.8s , <10M
Hint :

2021.9.16

加強測資(1 ≤ N, x, y ≤ 1,000,000),並 rejudge 所有公開試題後程式碼

註:已於日前結束的測驗內成績不受影響

Tags:
Greedy
出處:
110學年度hgsh校內賽 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
27902
linjiajia094... (君莫笑)
g310
都是cin惹的禍
66 2021-11-04 22:19
27164
r1cky (木叢欉木叢)
g310
Java 解題心得
246 2021-09-15 21:28