b134. 有趣的分數 - 旦旦解題農場

內容

在一個神奇的國度裡，他們的分數加法非常有趣

$\frac{3}{4}+\frac{2}{5}=\frac{3+2}{4+5}$

現在給你$N$個分數，告訴你必定要取$K$個，請問你可以拿到的最大值是多少

輸入說明

第一行有一數字$N,K$，代表接下來有$N$個分數，並且一定要選擇$K$個分數

第二行有$N$個數字$a_i$

第三行有$N$個數字$b_i$

代表分數$\frac{a_i}{b_i}$

輸出說明

請輸出最大的答案介於哪兩個連續整數之間（輸出 $N$ 若且唯若答案介於[N,N+1)之間)，如果最大的答案本身即為整數$N$，輸出$N$即可

範例輸入

#第一筆測資
3 2
500 0 200
5 1 6
#第二筆測資
4 2
100 200 700 900
5 6 7 9

範例輸出

#第一筆答案
83
#第二筆答案
100

測資資訊：

記憶體限制： 64 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 , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

對於$50\%$的測資, $1 \leq K \leq N \leq 20,0\leq a_i, b_i \leq 1000$

對於$100\%$的測資,$1 \leq K \leq N \leq 100000, 0 \leq a_i ,b_i\leq 10^6, b_i \neq 0$

對於第一筆測資，你可以取

$\frac{500}{5} + \frac{0}{1} = \frac{500}{6} \approx 83.3$

標籤:

出處:

[管理者：

william1010121 (郭勝威)

]

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