QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 5177. 摩斯电码 2.0

Statistics

题目描述

考虑一种有理有据的议会席位分配方法。

假设 $n$ 个政党的最终票分别为 $V_i$,分配 $m$ 个席位,规则如下:

初始议会为空,每个政党有 $0$ 个席位。

对于每个政党,计算 $Q_i = \frac{V_i}{S_i+1}$ 最大的政党 $p$, 其中 $S_i$ 表示第 $i$ 个政党已经获得的席位。若有多个政党 $Q_i$ 相同,取编号最小的那个。

分配给政党 $p$ 一个席位,重复上步,直到分配完 $m$ 个席位。

现在投票还在进行,每个政党当前得票数为 $v_i$,还有 $n$ 堆群众未进行投票,其中第 $i$ 堆群众人数为 $a_i$,且其中每个人可以选择投给第 $i$ 或 $i + 1$ 个政党,不能弃权。特殊的,第 $n$ 堆群众可以投给第 $n$ 和 $1$ 个政党。

请计算第 $1$ 个政党最多能获得多少个席位。

输入格式

第一行两个整数 $n,m$。

接下来一行 $n$ 个整数表示 $v_i$。

接下来一行 $n$ 个整数 $a_i$。

输出格式

一个整数表示答案。

样例输入1

3 3
10 5 6
3 1 2

样例输出1

2

样例输入2

5 5
2 1 3 3 3
2 4 2 5 5

样例输出2

2

数据范围

对于所有数据:$2 \le n \le 10^5,m \le 10^9,v_i,a_i \le 10^9,v_i>0$。

$\text{Subtask 1 (10 pts)}$:$n,m \le 5,v_i,a_i \le 5$。

$\text{Subtask 2 (10 pts)}$:$n \le 50,m \le 100,v_i,a_i \le 250$。

$\text{Subtask 3 (20 pts)}$:$n \le 50,m \le 500$。

$\text{Subtask 4 (20 pts)}$:$n \le 1000,m \le 1000$。

$\text{Subtask 5 (20 pts)}$:$n \le 10^4$。

$\text{Subtask 6 (20 pts)}$:无特殊限制。

时间限制:$\text{1s}$。

空间限制:$\text{256MB}$。