#P17810. [ICPC 2019 Nanchang R] Eating Plan
[ICPC 2019 Nanchang R] Eating Plan
题目描述
Bob 现在饿了,需要吃点食物。Alice 把 盘食物摆在他面前,编号从 到 。Alice 告诉他只能吃连续编号的若干盘食物,否则他会食物中毒。例如,若有 盘食物,他可以吃第 、 和 盘中的食物,但不能吃第 、 和 盘中的食物,因为中间隔着第 盘,不连续。此外,如果他选择吃第 盘食物,他必须吃掉该盘中的所有食物。
Bob 的胃有一个奇怪的特点:如果其中的食物至少有 kg,胃里的食物重量会反复减少 kg,直到严格低于 kg 为止。同样地,如果胃里食物的重量恰好等于 kg,他的胃就会变空。现在 Bob 希望吃最少的连续盘数,使得胃里最终剩下的食物不少于 kg。你能告诉他最少需要选择多少盘吗?
输入格式
第一行包含两个整数 和 (,),分别表示食物的盘数与查询的个数。
第二行包含 个整数 ,它是 的一个排列,表示第 盘食物有 kg,其中 。
第三行包含 个整数,第 个整数 ()表示一个查询的重量下限。
输出格式
共 行,每行输出一个整数,表示该查询中 Bob 最少需要选择的连续盘数。如果无法达到 Bob 的目标,输出 -1。
4 2
1 2 3 4
29 31
2
3
提示
翻译由 DeepSeek V4 Pro 完成