A3057 | Kingdom Game I
来源官方 / 2024
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Yuilice最近在玩一款策略游戏《Kind Kingdom》，游戏非常有趣，但是Yuilice想睡觉的时候也可以让电脑运行脚本玩，所以他请你帮他写一个这样的脚本达到效果。
游戏规则如下:
1. 《Kind Kingdom》当中，你初始会被分配 $n$ 个居民，每个居民都有他自己的生活成本 $w_i$ 与对王国的贡献 $v_i$。
2. 当一个居民被分配到的生活成本 $S$ 低于他的生活成本 $w_i$ 他就会发起叛乱,对王国造成 $v_i$ 的损失。
3. 当一个居民的生活成本$S$达到$k\times w_i$时，他对于王国的共享也会随之变为 $k \times v_i$ ($k$一定为整数,并且向下取整) 。
4. 获胜的条件为王国的总贡献值 $Sum_v$ 大于等于 $M$。
因为保留下来的生活成本可以被继承到下一把当中，所以Yuilice想知道，他给每一个居民的生活成本 $S$，最小的 $Min_S$ 为多少？
游戏规则如下:
1. 《Kind Kingdom》当中，你初始会被分配 $n$ 个居民，每个居民都有他自己的生活成本 $w_i$ 与对王国的贡献 $v_i$。
2. 当一个居民被分配到的生活成本 $S$ 低于他的生活成本 $w_i$ 他就会发起叛乱,对王国造成 $v_i$ 的损失。
3. 当一个居民的生活成本$S$达到$k\times w_i$时，他对于王国的共享也会随之变为 $k \times v_i$ ($k$一定为整数,并且向下取整) 。
4. 获胜的条件为王国的总贡献值 $Sum_v$ 大于等于 $M$。
因为保留下来的生活成本可以被继承到下一把当中，所以Yuilice想知道，他给每一个居民的生活成本 $S$，最小的 $Min_S$ 为多少？
输入格式
第一行共输入两个整数 $n,M$ - 代表共有 $n$ 个居民和通关条件$M$点贡献值
第二行共输入 $n$ 个整数,代表 $w_1,w_2,w_3....w_n$ - 代表每位居民的生活成本
第二行共输入 $n$ 个整数,代表 $v_1,v_2,v_3....v_n$。 - 代表每位居民的贡献值
第二行共输入 $n$ 个整数,代表 $w_1,w_2,w_3....w_n$ - 代表每位居民的生活成本
第二行共输入 $n$ 个整数,代表 $v_1,v_2,v_3....v_n$。 - 代表每位居民的贡献值
输出格式
输出最小的生活成本 $S$.
输入输出样例
输入 #1
5 100 10 20 30 40 50 10 5 10 10 20
输出 #1
50
输入 #2
5 100 10 100 100 100 100 104 1 1 1 1
输出 #2
10
当我们设定每个居民的生活成本$S = 50$的时候，每位居民提供的价值如下:
1. $Sum_{v1} = 5 \times 10 = 50$
2. $Sum_{v2} = 2 \times 5 = 10$
3. $Sum_{v3} = 1 \times 10 = 10$
4. $Sum_{v4} = 1 \times 10 = 10$
5. $Sum_{v5} = 1 \times 20 = 20$
最终价值总和为$100$ 刚好等于$M$通关。
对于$30\%$的数据,$1 \leq n \leq 10 , 10 \leq M \leq 10^3 , 1 \leq w_i \leq 10^3 ,1 \leq v_i \leq 10^3$
对于$50\%$的数据,$1 \leq n \leq 10^5 , 10 \leq M \leq 10^3 , 1 \leq w_i \leq 10^3 ,1 \leq v_i \leq 10^3$
对于$100\%$的数据,$1 \leq n \leq 2 \times 10^5 , 10 \leq M \leq 10^6 , 1 \leq w_i \leq 10^6 ,10^4 \leq v_i \leq 10^6$
1. $Sum_{v1} = 5 \times 10 = 50$
2. $Sum_{v2} = 2 \times 5 = 10$
3. $Sum_{v3} = 1 \times 10 = 10$
4. $Sum_{v4} = 1 \times 10 = 10$
5. $Sum_{v5} = 1 \times 20 = 20$
最终价值总和为$100$ 刚好等于$M$通关。
对于$30\%$的数据,$1 \leq n \leq 10 , 10 \leq M \leq 10^3 , 1 \leq w_i \leq 10^3 ,1 \leq v_i \leq 10^3$
对于$50\%$的数据,$1 \leq n \leq 10^5 , 10 \leq M \leq 10^3 , 1 \leq w_i \leq 10^3 ,1 \leq v_i \leq 10^3$
对于$100\%$的数据,$1 \leq n \leq 2 \times 10^5 , 10 \leq M \leq 10^6 , 1 \leq w_i \leq 10^6 ,10^4 \leq v_i \leq 10^6$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？