luogu#P9468. [EGOI2023] Candy / 糖果
[EGOI2023] Candy / 糖果
题目背景
Day 2 Problem B.
题面译自 EGOI2023 candy。
题目描述
在伊卡古城,据说有一座宫殿,其财富超乎想象。在其中,一个走廊中有 盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量,就可以拿走任意多的糖果。
装糖果的盒子被从左到右编号为 到 。在盒子 中,剩余有 单位的糖果,其中 是一个非负整数。
作为宫殿的守护者,你需要移动这些盒子,使得有很多糖果的盒子更靠近入口。
你已知数组 ,以及整数 和 。在一次操作中,你被允许交换 中的任意两个相邻元素。要使得数组前 个元素的和至少为 ,至少需要多少次操作?
输入格式
第一行三个整数 。
第二行 个整数 。
输出格式
如果不可能达成目标,输出 NO
。
否则,输出一个整数,表示最少操作数。
6 2 27
10 4 20 6 3 3
1
6 5 5000000000
1000000000 1000000000 0 1000000000 1000000000 1000000000
3
3 2 100
20 30 60
NO
1 1 100
100
0
提示
样例 解释
在样例 中,前两个元素的和应当至少为 。一次相邻元素的交换就可以达成目标:交换 和 。在这次交换后,数组变成 10 20 4 6 3 3
,前两个元素的和为 。
样例 解释
在样例 中,这个 必须一路移动到数组末尾;这需要 次交换。
样例 解释
在样例 中,不可能使得前两个元素和至少为 ;我们能做到的最好结果是 。
数据范围
对于全部数据,,,,。
- 子任务一( 分):,,。
- 子任务二( 分):。
- 子任务三( 分):。
- 子任务四( 分):。
- 子任务五( 分):无特殊限制。
提示
答案可能不在 位整型范围内,如果你使用 C++ 语言,请注意溢出的可能。