102273: [AtCoder]ABC227 D - Project Planning
Description
Score : $400$ points
Problem Statement
KEYENCE has $N$ departments, where $A_i$ employees belong to the $i$-th department $(1 \leq i \leq N)$. No employee belongs to multiple departments.
The company is planning cross-departmental projects. Each project will be composed of exactly $K$ employees chosen from $K$ distinct departments.
At most how many projects can be made? No employee can participate in multiple projects.
Constraints
- $1 \leq K \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^{12}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the maximum possible number of projects.
Sample Input 1
3 3 2 3 4
Sample Output 1
2
There can be two projects, each composed of three employees from distinct departments.
Sample Input 2
4 2 1 1 3 4
Sample Output 2
4
Sample Input 3
4 3 1 1 3 4
Sample Output 3
2
Input
题意翻译
一个公司有 $N$ 个部门，第 $i$ 个部门有 $A_i$ 名员工。不会有员工同时属于多个不同部门。 公司计划建立若干个横跨不同部门的项目，一个项目必须由来自不同部门的恰好 $K$ 名员工组成。 问最多可以同时建立多少个项目？Output
得分：400分
问题描述
KEYENCE 公司有 N 个部门，其中第 i 个部门有 A_i 名员工（1 ≤ i ≤ N）。没有员工属于多个部门。
公司正在计划跨部门项目。每个项目将由从 K 个不同的部门中选择的恰好 K 名员工组成。
最多可以创建多少个项目？任何员工都不能参加多个项目。
约束
- 1 ≤ K ≤ N ≤ 2 × 10^5
- 1 ≤ A_i ≤ 10^{12}
- 输入中的所有值都是整数。
输入
从标准输入以以下格式给出输入：
$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印可能的最大项目数。
样例输入 1
3 3 2 3 4
样例输出 1
2
可以创建两个项目，每个项目由来自不同部门的三名员工组成。
样例输入 2
4 2 1 1 3 4
样例输出 2
4
样例输入 3
4 3 1 1 3 4
样例输出 3
2