#1711. 摩斯电码 2.0

    ID: 1711 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1059来源:qoj.ac数据:公开样例

摩斯电码 2.0

摩斯电码 2.0

题目描述

标题: 摩斯电码 2.0 - Problem - QOJ.ac

#5177. 摩斯电码 2.0

Statistics

The problem was used in the following contests:

题目描述

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

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

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

对于每个政党,计算 Qi=ViSi+1 最大的政党 p, 其中 Si 表示第 i 个政党已经获得的席位。若有多个政党 Qi 相同,取编号最小的那个。

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

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

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

输入格式

第一行两个整数 n,m。

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

接下来一行 n 个整数 ai。

输出格式

一个整数表示答案。

样例输入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≤n≤105,m≤109,vi,ai≤109,vi>0。

Subtask 1 (10 pts):n,m≤5,vi,ai≤5。

Subtask 2 (10 pts):n≤50,m≤100,vi,ai≤250。

Subtask 3 (20 pts):n≤50,m≤500。

Subtask 4 (20 pts):n≤1000,m≤1000。

Subtask 5 (20 pts):n≤104。

Subtask 6 (20 pts):无特殊限制。

时间限制:1s。

空间限制:256MB。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
10 5 6
3 1 2
2

样例 2

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