终别【牛客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, i1][i,i1]或仅一个位置左侧斩击数pre[i-1]右侧斩击数sur[i2]取所有组合的最小值。2. 算法实现输入与初始化读取n nn和血量数组a同时复制一份到b用于右侧贪心。若n ≤ 2 n \le 2n≤2直接输出0因为魔法或斩击可以全部消灭但最少斩击次数为0 00魔法直接消灭两个。左侧贪心构建pre遍历i 1 → n i 1 \to ni1→n若a[i] 0则必须进行a[i]次斩击覆盖i , i 1 , i 2 i, i1, i2i,i1,i2pre[i] pre[i-1] a[i]a[i1] - a[i]a[i2] - a[i]否则pre[i] pre[i-1]。右侧贪心构建sur遍历i n → 2 i n \to 2in→2用备份数组b若b[i] 0则进行b[i]次斩击覆盖i , i − 1 , i − 2 i, i-1, i-2i,i−1,i−2sur[i] sur[i1] b[i]b[i-1] - b[i]b[i-2] - b[i]否则sur[i] sur[i1]。枚举魔法位置初始答案ans pre[n]不使用魔法。枚举魔法左端点i ii1 ≤ i ≤ n 1 \le i \le n1≤i≤n允许仅一个位置总斩击数 pre[i-1] sur[i2]更新ans min(ans, ...)。输出ans。3. 复杂度分析时间复杂度O ( n ) O(n)O(n)只需三次线性扫描左侧、右侧、枚举。空间复杂度O ( n ) O(n)O(n)存储原数组、备份数组及前后缀数组。总结通过贪心分别处理左右两段将魔法位置作为分割点利用前缀与后缀的最优斩击数快速计算总代价避免了复杂的动态规划。贪心的正确性基于“斩击尽量覆盖未处理区域”的直观最优策略。整体思路清晰高效适用于10 6 10^6106规模的数据。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXN1000000100;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 i1;in;i){scanf(%lld,a[i]);b[i]a[i];}if(n2){printf(0\n);return0;}for(ll i1;in;i){if(a[i]0){pre[i]pre[i-1]a[i];a[i1]-a[i];a[i2]-a[i];}elsepre[i]pre[i-1];}for(ll in;i2;i--){if(b[i]0){sur[i]sur[i1]b[i];b[i-1]-b[i];b[i-2]-b[i];}elsesur[i]sur[i1];}ll anspre[n];for(ll i1;in;i)ansmin(ans,pre[i-1]sur[i2]);printf(%lld\n,ans);return0;}