终别【牛客tracker 每日一题】
终别
时间限制：1 秒
空间限制：256 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
不想对你说句感谢，
始终将它埋藏心中，
离别总是在纯洁无瑕的，
梦境过后 悄然而至，
纷纷飘落在双手间的碎片，
无论何时 无论何时都要紧紧握住，
敢于笑到最后的那份坚强，
已然深有体会。
——《Last Regrets》
小C要退役了，可他依然喜欢信息以及从信息中认识的那些人，无论他们是否曾相识……
珂朵莉讨厌共n nn只十七兽，它们站成一排，每只十七兽站在一个位置上，她的斩击可以连续3 33个位置上的十七兽（也可以只使一只，或相邻两只受到伤害），每一只受到一点伤害，当一个十七兽的血量归零时，视为该十七兽被消灭（但位置仍然保留），她还拥有一个魔法，魔法可以在战斗中的任意时刻使用，但只能使用一次，可以直接消灭相邻的2 22个位置上的十七兽（只有一只也可以使用，位置仍然保留）。请问，她最少需要挥出多少次斩击，能够消灭所有十七兽？因为她已经筋疲力尽了，所以需要聪明的你来帮她她！
输入描述
第一行一个数n nn，分别表示十七兽的数量。
第二行共n nn个整数，第i ii个整数表示a i a_iai，表示第i ii只十七兽的血量。
数据范围：1 ≤ n ≤ 10 6 , 0 ≤ a i ≤ 10 9 1 \le n \le 10^6,\ 0 \le a_i \le 10^91≤n≤106,0≤ai≤109。
输出描述
共一个数，表示珂朵莉需要挥出的斩击数。
示例 1
输入：
3 2 0 1输出：
1说明：
对1 , 2 1, 21,2位置使用魔法，对2 22造成伤害，共斩击1 11次。
示例 2
输入：
10 3 2 2 2 3 1 1 1 2 1 2输出：
5说明：
对1 , 2 1, 21,2使用魔法，接下来的斩击位置为：
3 4 5 3 4 5 5 6 7 8 9 10 8 9 10解题思路
本题是贪心 + 前后缀预处理的经典题型。需要在一排怪物中，用“斩击”和一次“魔法”将其全部消灭，求最少斩击次数。斩击可以选择连续1 ∼ 3 1\sim31∼3个位置各造成1 11点伤害；魔法能直接消灭相邻两个位置（或仅一个）。由于魔法只能使用一次，可以将问题拆成左右两个独立部分，分别用贪心求出最少斩击数，再枚举魔法位置取最优。
1. 问题等价转化
- 斩击的贪心性质：对于任意一个怪物，若它位于已处理区间的最左端（或最右端），为了消灭它，必须至少对它本身造成等于其血量的斩击。因为斩击可以覆盖连续3 33个位置，最优做法是把斩击起点放在当前怪物上，并让斩击覆盖其右侧（或左侧）尽可能多的怪物，这样能最大化每次斩击的收益，避免浪费伤害到已处理的区域。
- 分治思想：使用魔法后，被魔法直接消灭的两个位置将整个序列分成左右两段，左右两段互不影响。因此总斩击数 = 左段从左侧贪心所需的斩击数 + 右段从右侧贪心所需的斩击数。
- 状态定义：
pre[i]：从左到右贪心处理完前i ii个位置所需的最少斩击数。sur[i]：从右到左贪心处理完第i ii到第n nn个位置所需的最少斩击数。
- 答案：不使用魔法的答案为
pre[n]；使用魔法时，枚举魔法覆盖的两个相邻位置[ i , i + 1 ] [i, i+1][i,i+1]（或仅一个位置），左侧斩击数pre[i-1]，右侧斩击数sur[i+2]，取所有组合的最小值。
2. 算法实现
- 输入与初始化：
- 读取n nn和血量数组
a，同时复制一份到b用于右侧贪心。 - 若n ≤ 2 n \le 2n≤2，直接输出
0（因为魔法或斩击可以全部消灭，但最少斩击次数为0 00，魔法直接消灭两个）。
- 读取n nn和血量数组
- 左侧贪心（构建
pre）：- 遍历i = 1 → n i = 1 \to ni=1→n：
- 若
a[i] > 0，则必须进行a[i]次斩击，覆盖i , i + 1 , i + 2 i, i+1, i+2i,i+1,i+2：pre[i] = pre[i-1] + a[i]a[i+1] -= a[i]，a[i+2] -= a[i]
- 否则
pre[i] = pre[i-1]。
- 若
- 遍历i = 1 → n i = 1 \to ni=1→n：
- 右侧贪心（构建
sur）：- 遍历i = n → 2 i = n \to 2i=n→2（用备份数组
b）：- 若
b[i] > 0，则进行b[i]次斩击，覆盖i , i − 1 , i − 2 i, i-1, i-2i,i−1,i−2：sur[i] = sur[i+1] + b[i]b[i-1] -= b[i]，b[i-2] -= b[i]
- 否则
sur[i] = sur[i+1]。
- 若
- 遍历i = n → 2 i = n \to 2i=n→2（用备份数组
- 枚举魔法位置：
- 初始答案
ans = pre[n]（不使用魔法）。 - 枚举魔法左端点i ii（1 ≤ i ≤ n 1 \le i \le n1≤i≤n，允许仅一个位置）：
- 总斩击数 =
pre[i-1] + sur[i+2] - 更新
ans = min(ans, ...)。
- 总斩击数 =
- 初始答案
- 输出
ans。
3. 复杂度分析
- 时间复杂度：O ( n ) O(n)O(n)，只需三次线性扫描（左侧、右侧、枚举）。
- 空间复杂度：O ( n ) O(n)O(n)，存储原数组、备份数组及前后缀数组。
总结
通过贪心分别处理左右两段，将魔法位置作为分割点，利用前缀与后缀的最优斩击数快速计算总代价，避免了复杂的动态规划。贪心的正确性基于“斩击尽量覆盖未处理区域”的直观最优策略。整体思路清晰高效，适用于10 6 10^6106规模的数据。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll MAXN=1000000+100;ll pre[MAXN],sur[MAXN],a[MAXN],b[MAXN];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i];}if(n<=2){printf("0\n");return0;}for(ll i=1;i<=n;i++){if(a[i]>0){pre[i]=pre[i-1]+a[i];a[i+1]-=a[i];a[i+2]-=a[i];}elsepre[i]=pre[i-1];}for(ll i=n;i>=2;i--){if(b[i]>0){sur[i]=sur[i+1]+b[i];b[i-1]-=b[i];b[i-2]-=b[i];}elsesur[i]=sur[i+1];}ll ans=pre[n];for(ll i=1;i<=n;i++)ans=min(ans,pre[i-1]+sur[i+2]);printf("%lld\n",ans);return0;}