#3735. 分饼干
分饼干
题目描述
有 个小朋友排成一排,第 个小朋友的饥饿程度为 。老师准备了若干块饼干,每块饼干只能分给一个小朋友,并且每个小朋友最多分到一块。
老师希望所有小朋友都满意。一个小朋友满意当且仅当他分到的饼干数量(0 或 1)满足:
- 如果他的饥饿程度为 ,那么他至少需要 块饼干才能满意。
但每个小朋友最多只有 1 块饼干,因此只有 的小朋友才可能满意。
然而,老师发现这个要求太苛刻了。于是他修改了规则:只要每个小朋友分到的饼干数不少于他相邻小朋友分到的饼干数,他就满意。
具体地,对于第 个小朋友(),若他分到 块饼干(),则他满意当且仅当:
- 若 ,则 ;
- 若 ,则 。
注意:上述两个条件需要同时满足(若相邻小朋友不存在则忽略该条件)。
老师希望用尽可能少的饼干让所有小朋友都满意。请你求出最少需要多少块饼干。如果无法让所有小朋友都满意,输出 -1。
输入格式
第一行一个整数 ,表示小朋友的数量。
第二行 个整数 ,表示每个小朋友的饥饿程度。
输出格式
输出一个整数,表示最少需要的饼干数;若无法让所有小朋友都满意,输出 -1。
样例
1
5
0
3
2 0 1
0
说明/提示
数据范围
- 对于 的数据,。
- 对于 的数据,,。
样例解释
样例 1:只有 1 个小朋友,他分到 0 块饼干即可满意(没有相邻小朋友),因此答案为 0。
样例 2:可以给第 2 个小朋友 1 块饼干,其他小朋友 0 块。此时第 1 个小朋友(0 块)的右邻居是 1 块,不满足 ,因此第 1 个小朋友不满意。
尝试给第 1、2 个小朋友各 1 块饼干:。第 1 个小朋友满足 ();第 2 个小朋友满足 ()且 ();第 3 个小朋友满足 ? 不成立,因此第 3 个小朋友不满意。
尝试 :所有小朋友都满足,需要 3 块饼干。
尝试 :第 1 个小朋友满足 ();第 2 个小朋友满足 且 ();第 3 个小朋友满足 ()。所有小朋友都满意,需要 0 块饼干。
因此答案为 0。
注意:本题中 实际上不影响答案(因为规则修改后与饥饿程度无关),但输入中仍会给出。
解析
分饼干 题解
解题思路
题目要求每个小朋友都满意。对于第 个小朋友,满意条件为:
- 若 ,则 ;
- 若 ,则 。
把相邻两个小朋友 和 的条件放在一起看:
- 第 个小朋友要求 ;
- 第 个小朋友要求 。
两者同时成立,只能有 。由于这个结论对每一对相邻小朋友都成立,所以所有 必须全部相等。
每个 ,因此所有小朋友要么都分到 块,要么都分到 块。全部取 时总饼干数为 ,全部取 时总饼干数为 。显然最小值为 。
注意:题目中的饥饿程度 在修改规则后完全不参与满意条件,因此读入后无需使用。
算法选择理由
本题的关键是发现“所有 必须相等”这一结构性质。发现后直接输出 即可,不需要枚举或动态规划。虽然 很大,但答案与它们无关。
复杂度分析
- 时间复杂度:,仅需读入输入。
- 空间复杂度:(若边读边丢弃可做到 )。
在 的数据范围内,该做法远低于时间限制。
来源
AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心