bzoj#P1168. [BalticOI 2008] Gloves
[BalticOI 2008] Gloves
题目描述
手套被放在了两个抽屉里,所有的左手套放在左边的抽屉里,所有的右手套放在右边的抽屉里。手套一共有 种颜色,已知两个抽屉每种颜色的手套各有多少只,如果随便在左边拿一只,右边拿一只很可能会造成拿到一只红色的左手套和一只蓝色右手套……现想知道应该从左边的抽屉取出多少只左手套(设为 )、右边的抽屉取出多少只右手套(设为 ),满足至少可以找到一对匹配的手套(即颜色相同),并且 最小。
如果有多个 满足 最小,你希望满足 尽可能的小。
不妨设每个抽屉里每只手套被取出的概率是等价的。
输入格式
第一行中有一个正整数 ,表示颜色的种数。
第二行有 个非负整数 ,表示左抽屉中每种颜色的左手套的个数。
第三行有 个非负整数 ,表示右抽屉中每种颜色的右手套的个数。
输出格式
输出满足题目条件的 。
4
0 7 1 6
1 5 0 6
28
数据范围
对于 的测试数据,。