c150. C. 比賽練習 - 大魏線上解題系統

Content

AC與WA是多年的好友，也都是正在準備彰雲嘉複賽的熱血競程校隊選手。比賽迫在眉睫，他們共有 $N$ 天密集備戰的時間。AC擅長訂定計畫，能每天根據自己的實力與狀態決定是否練習；而WA則比較隨性及懶惰，只有在AC練習的隔天才會想練習。此外，對於AC和WA能夠準備比賽的這 $N$ 天，若AC選擇在第 $i(1 \le i \le N)$ 天練習，他可以在那天解出 $A_i$ 題；相似地，若WA選擇在第 $j(1 \le j \le N)$ 天練習，他可以在那天解出 $B_j$ 題。為了在比賽中拉開與WA的差距，AC希望精心安排練習日程，讓自己練習的題目數遠超過WA。請問AC最多能比WA多解多少題？

Input

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$
$B_1$ $B_2$ $B_3$ $\dots$ $B_N$

$1\le N\le 100$
$1\le A_i,B_j\le 100$

Output

$ans$

輸出一個整數，表示AC最多能比WA多解出的題目數量

Sample Input #1

2
3 2
2 1

Sample Output #1

Sample Input #2

1
5
8

Sample Output #2

Sample Input #3

6
8 2 5 6 2 6
8 2 7 4 3 4

Sample Output #3

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1K
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1K
公開測資點#17 (5%): 1.0s , <1K
公開測資點#18 (5%): 1.0s , <1K
公開測資點#19 (5%): 1.0s , <1K

Hint ：

在範例 $1$ 中，AC 應該在第 $1$ 天與第 $2$ 天練習，這樣AC的解題數為 $5$，WA的解題數則為 $1$，可知道AC最多能比WA多練習 $4$ 題。
在範例 $3$ 中，AC應該在第 $1$ 天、第 $3$ 天、第 $4$ 天和第 $6$ 天練習，這樣AC的解題數為 $25$，WA的解題數則為 $9$，可知道AC最多能比WA多練習 $16$ 題。

Tags:

greedy

出處:

114學年校內能競選拔 [管理者： jackhuang(fijjj) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」