{"problem":{"name":"[EGOI 2023] Candy / 糖果","description":{"content":"在伊卡古城，据说有一座宫殿，其财富超乎想象。在其中，一个走廊中有 $N$ 盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量，就可以拿走任意多的糖果。 装糖果的盒子被从左到右编号为 $0$ 到 $N-1$。在盒子 $i$ 中，剩余有 $a_i$ 单位的糖果，其中 $a_i$ 是一个非负整数。 作为宫殿的守护者，你需要移动这些盒子，使得有很多糖果的盒子更靠近入口。 你已知数组 $a_0","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9468"},"statements":[{"statement_type":"Markdown","content":"在伊卡古城，据说有一座宫殿，其财富超乎想象。在其中，一个走廊中有 $N$ 盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量，就可以拿走任意多的糖果。\n\n装糖果的盒子被从左到右编号为 $0$ 到 $N-1$。在盒子 $i$ 中，剩余有 $a_i$ 单位的糖果，其中 $a_i$ 是一个非负整数。\n\n作为宫殿的守护者，你需要移动这些盒子，使得有很多糖果的盒子更靠近入口。\n\n你已知数组 $a_0,a_1,\\cdots,a_{N-1}$，以及整数 $F$ 和 $T$。在一次操作中，你被允许交换 $a_0,a_1,\\cdots,a_{N-1}$ 中的任意两个**相邻**元素。要使得数组前 $F$ 个元素的和至少为 $T$，至少需要多少次操作？\n\n## Input\n\n第一行三个整数 $N,F,T$。\n\n第二行 $N$ 个整数 $a_0,a_1,\\cdots,a_{N-1}$。\n\n## Output\n\n如果不可能达成目标，输出 `NO`。\n\n否则，输出一个整数，表示最少操作数。\n\n[samples]\n\n## Background\n\nDay 2 Problem B.\n\n题面译自 [EGOI2023 candy](https://egoi23.se/assets/tasks/day2/candy.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例 $1$ 解释**\n\n在样例 $1$ 中，前两个元素的和应当至少为 $27$。一次相邻元素的交换就可以达成目标：交换 $4$ 和 $20$。在这次交换后，数组变成 `10 20 4 6 3 3`，前两个元素的和为 $10+20=30\\ge 27$。\n\n---\n\n**样例 $2$ 解释**\n\n在样例 $2$ 中，这个 $0$ 必须一路移动到数组末尾；这需要 $3$ 次交换。\n\n---\n\n**样例 $3$ 解释**\n\n在样例 $3$ 中，不可能使得前两个元素和至少为 $100$；我们能做到的最好结果是 $60+30=90$。\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le N\\le 100$，$1\\le F\\le N$，$0\\le T\\le 10^{11}$，$0\\le a_i\\le 10^9$。\n\n- 子任务一（$6$ 分）：$N\\le 2$，$a_i\\le 100$，$T\\le 10^9$。\n- 子任务二（$19$ 分）：$a_i\\le 1$。\n- 子任务三（$16$ 分）：$N\\le 20$。\n- 子任务四（$30$ 分）：$a_i\\le 100$。\n- 子任务五（$29$ 分）：无特殊限制。\n\n---\n\n**提示**\n\n答案可能不在 $32$ 位整型范围内，如果你使用 C++ 语言，请注意溢出的可能。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9468","tags":["动态规划 DP","2023","O2优化","EGOI（欧洲/女生）"],"sample_group":[["6 2 27\n10 4 20 6 3 3","1"],["6 5 5000000000\n1000000000 1000000000 0 1000000000 1000000000 1000000000","3"],["3 2 100\n20 30 60","NO"],["1 1 100\n100","0"]],"created_at":"2026-03-03 11:09:25"}}