718 . 最大平均區間
TopCoder
Tags
Description
學姐最近開始打工，第 $i$ 天她賺了 $A_i$ 塊錢。她決定跟朋友炫耀她平均一天能賺多少錢，所以她打算找 $L$ 和 $R$ 使得在第 $L$ 天到第 $R$ 天之間每天平均賺的錢最多，但是如果這個期間只有一天的話會被他的朋友抓包，換句話說，學姐想要找 $L, R$ 使得 $[A_L, A_{L+1}, \cdots, A_R]$ 的平均最大且 $L \ne R$ 。請幫學姐找到最好的平均日薪吧！
Input Format
輸入有兩行，第一行包含一個正整數 $N$，代表學姐打工了 $N$ 天，第二行有 $N$ 個正整數，第 $i$ 個正整數是 $A_i$，代表第 $i$ 天打工的薪資。
- $2 \le N \le 3 \cdot 10^ 5$
- $0 \le A_i \le 10^ 8$
Output Format
輸出只有一行，包含兩個正整數 $P$ 和 $Q$，代表最大的平均日薪為 $\frac{P}{Q}$，這必須是一個最簡分數，也就是說 $P, Q$ 互質。
Sample Input 1
5
1 3 4 2 3
1 3 4 2 3
Sample Output 1
7 2
Sample Input 2
3
0 0 0
0 0 0
Sample Output 2
0 1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~19 | 無額外限制 | 100 |