No.3758 Fan Meeting
タグ : / 解いたユーザー数 64
作問者 :
ei1333333
/ テスター :
ei13333333
kyoprouno
Problem Statement
In the virtual space "Tsukuyomi", Yachiyo is going to interact with $N$ fans.
Yachiyo's original size is $S$. Before the interactions begin, Yachiyo may freely divide her size to create any number of clones.
The number of clones is a positive integer, and the size of each clone is a positive real number. The sum of the sizes of all clones must be $S$.
The expectation level of fan $i$ is $A_i$. Fan $i$ is satisfied if one of the following conditions is met.
- The fan interacts for $1$ unit of time with a clone whose size is greater than $A_i$.
- The fan interacts for $A_i$ units of time with any clone, regardless of its size.
The interactions follow these rules.
- After the interactions have begun, the number of clones and their sizes cannot be changed.
- Each fan interacts continuously with exactly $1$ clone. An interaction cannot be interrupted, and the clone a fan interacts with cannot be changed midway.
- Different clones can interact at the same time.
- $1$ clone can interact with only $1$ fan at a time. However, as long as the times do not overlap, $1$ clone may interact with multiple fans in turn.
When the interactions begin at time $0$, find the minimum time required until all fans are satisfied. It can be proved that the answer is an integer under the conditions of this problem.
Constraints
- $1 \leq N \leq 3 \times 10^5$
- $1 \leq S \leq 10^9$
- $1 \leq A_i \leq 10^9$
- All input values are integers
Input
$N$ $S$ $A_1$ $A_2$ $\cdots$ $A_n$
Output
Print the answer on 1 line.
Sample
Sample 1
Input
3 8 4 3 2
Output
2
Create clones of sizes $5$ and $3$, $1$ of each.
The clone of size $5$ interacts with fan $1$ and then fan $2$ for $1$ unit of time each, and at the same time, the clone of size $3$ interacts with fan $3$ for $1$ unit of time. Then everyone is satisfied in $2$ units of time.
To satisfy everyone in $1$ unit of time, clones with sizes greater than $4,3,2$ respectively would be needed, but their total cannot be made $8$. Therefore, the answer is $2$.
Sample 2
Input
1 5 5
Output
5
Every clone has size at most $5$, so a clone of size greater than $5$ cannot be created.
Therefore, fan $1$ must interact with some clone for $5$ units of time, and the answer is $5$.
Sample 3
Input
4 20 1 2 3 4
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。