#3735. 分饼干

分饼干

题目描述

有 nn 个小朋友排成一排,第 ii 个小朋友的饥饿程度为 aia_i。老师准备了若干块饼干,每块饼干只能分给一个小朋友,并且每个小朋友最多分到一块。

老师希望所有小朋友都满意。一个小朋友满意当且仅当他分到的饼干数量(0 或 1)满足:

  • 如果他的饥饿程度为 aia_i,那么他至少需要 aia_i 块饼干才能满意。

但每个小朋友最多只有 1 块饼干,因此只有 ai≤1a_i \le 1 的小朋友才可能满意。

然而,老师发现这个要求太苛刻了。于是他修改了规则:只要每个小朋友分到的饼干数不少于他相邻小朋友分到的饼干数,他就满意。

具体地,对于第 ii 个小朋友(1≤i≤n1 \le i \le n),若他分到 bib_i 块饼干(bi∈{0,1}b_i \in \{0,1\}),则他满意当且仅当:

  • 若 i>1i>1,则 bi≥bi−1b_i \ge b_{i-1};
  • 若 i<ni<n,则 bi≥bi+1b_i \ge b_{i+1}。

注意:上述两个条件需要同时满足(若相邻小朋友不存在则忽略该条件)。

老师希望用尽可能少的饼干让所有小朋友都满意。请你求出最少需要多少块饼干。如果无法让所有小朋友都满意,输出 -1。

输入格式

第一行一个整数 nn,表示小朋友的数量。

第二行 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示每个小朋友的饥饿程度。

输出格式

输出一个整数,表示最少需要的饼干数;若无法让所有小朋友都满意,输出 -1。

样例

1
5 
0 
3
2 0 1 
0 

说明/提示

数据范围

  • 对于 30%30\% 的数据,1≤n≤101 \le n \le 10。
  • 对于 100%100\% 的数据,1≤n≤10001 \le n \le 1000,0≤ai≤1090 \le a_i \le 10^9。

样例解释

样例 1:只有 1 个小朋友,他分到 0 块饼干即可满意(没有相邻小朋友),因此答案为 0。

样例 2:可以给第 2 个小朋友 1 块饼干,其他小朋友 0 块。此时第 1 个小朋友(0 块)的右邻居是 1 块,不满足 b1≥b2b_1 \ge b_2,因此第 1 个小朋友不满意。

尝试给第 1、2 个小朋友各 1 块饼干:b=[1,1,0]b = [1,1,0]。第 1 个小朋友满足 b1≥b2b_1 \ge b_2(1≥11 \ge 1);第 2 个小朋友满足 b2≥b1b_2 \ge b_1(1≥11 \ge 1)且 b2≥b3b_2 \ge b_3(1≥01 \ge 0);第 3 个小朋友满足 b3≥b2b_3 \ge b_2?0≥10 \ge 1 不成立,因此第 3 个小朋友不满意。

尝试 b=[1,1,1]b = [1,1,1]:所有小朋友都满足,需要 3 块饼干。

尝试 b=[0,0,0]b = [0,0,0]:第 1 个小朋友满足 b1≥b2b_1 \ge b_2(0≥00 \ge 0);第 2 个小朋友满足 b2≥b1b_2 \ge b_1 且 b2≥b3b_2 \ge b_3(0≥00 \ge 0);第 3 个小朋友满足 b3≥b2b_3 \ge b_2(0≥00 \ge 0)。所有小朋友都满意,需要 0 块饼干。

因此答案为 0。

注意:本题中 aia_i 实际上不影响答案(因为规则修改后与饥饿程度无关),但输入中仍会给出。

解析

分饼干 题解

解题思路

题目要求每个小朋友都满意。对于第 ii 个小朋友,满意条件为:

  • 若 i>1i>1,则 bi≥bi−1b_i \ge b_{i-1};
  • 若 i<ni<n,则 bi≥bi+1b_i \ge b_{i+1}。

把相邻两个小朋友 ii 和 i+1i+1 的条件放在一起看:

  • 第 ii 个小朋友要求 bi≥bi+1b_i \ge b_{i+1};
  • 第 i+1i+1 个小朋友要求 bi+1≥bib_{i+1} \ge b_i。

两者同时成立,只能有 bi=bi+1b_i = b_{i+1}。由于这个结论对每一对相邻小朋友都成立,所以所有 bib_i 必须全部相等。

每个 bi∈{0,1}b_i \in \{0,1\},因此所有小朋友要么都分到 00 块,要么都分到 11 块。全部取 00 时总饼干数为 00,全部取 11 时总饼干数为 nn。显然最小值为 00。

注意:题目中的饥饿程度 aia_i 在修改规则后完全不参与满意条件,因此读入后无需使用。

算法选择理由

本题的关键是发现“所有 bib_i 必须相等”这一结构性质。发现后直接输出 00 即可,不需要枚举或动态规划。虽然 aia_i 很大,但答案与它们无关。

复杂度分析

  • 时间复杂度:O(n)O(n),仅需读入输入。
  • 空间复杂度:O(n)O(n)(若边读边丢弃可做到 O(1)O(1))。

在 n≤1000n \le 1000 的数据范围内,该做法远低于时间限制。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心