P16426 「YLLOI-R4-T2」听妈妈的话Link: https://www.luogu.com.cn/problem/P16426题目描述小 Y 养了n nn个会孵化出鸡的鸡蛋这些鸡蛋依次放入n nn个养殖箱第i ii个养殖箱的鸡蛋会在第a i a_iai​天孵化出来小 Y 可以随意决定这些鸡孵出来后的性别决定后不能再更改。在每一天结束后对于每两个相邻的养殖箱若里面的鸡蛋均已孵化且鸡为一公一母一母一公他们便会交配小 Y 会得到一个新鸡蛋该鸡蛋不用于孵化。第t tt天及其之后所有鸡就不再下蛋求小 Y 最多能得到多少个新鸡蛋。输入格式第一行两个正整数n , t n,tn,t。第二行n nn个正整数a i a_iai​。输出格式一个整数。输入输出样例 #1输入 #13 4 1 2 3输出 #13输入输出样例 #2输入 #25 5 1 1 1 1 1输出 #216说明/提示【样例解释#1】一种可能的情况第1 11天第1 11个养殖箱的鸡孵化出来小 Y 令其为公鸡。第2 22天第2 22个养殖箱的鸡孵化出来小 Y 令其为母鸡。第2 22天结束第1 11个养殖箱的鸡与第2 22个养殖箱的鸡产生一个鸡蛋。第3 33天第3 33个养殖箱的鸡孵化出来小 Y 令其为公鸡。第3 33天结束第1 11个养殖箱的鸡与第2 22个养殖箱的鸡产生一个鸡蛋第2 22个养殖箱的鸡与第3 33个养殖箱的鸡产生一个鸡蛋。第4 44天及其之后不再下蛋。共产生3 33个鸡蛋可以证明无论小 Y 怎样决定鸡的性别产生的鸡蛋数都不会超过3 33。【数据范围】本题采用捆绑测试。Subtask 120 ptsn , t ≤ 10 n,t\le 10n,t≤10。Subtask 220 pts∀ a i 1 \forall a_i1∀ai​1。Subtask 320 ptsn 2 n2n2。Subtask 420 ptsn , t ≤ 2000 n,t\le 2000n,t≤2000。Subtask 520 pts无特殊限制。对于全部数据保证1 ≤ n ≤ 10 6 1\le n\le 10^61≤n≤1061 ≤ a i , t ≤ 10 9 1\le a_i,t\le 10^91≤ai​,t≤109。Solution1. 题意n nn个会孵化出鸡的鸡蛋这些鸡蛋依次放入n nn个养殖箱第i ii个养殖箱的鸡蛋会在第a i a_iai​​ 天孵化出来可以事先决定其性别。在每一天结束后每两个相邻的养殖箱若里面的鸡蛋均已孵化且鸡为一公一母一母一公他们便会交配得到一枚鸡蛋。求t tt天前最多得到多少鸡蛋。2. 分析由于这些鸡的位置不能调换因此问题的难度巨幅降低很容易发现最优方案就是让所有的鸡按照“一公一母”交替排列即可。对于任意相邻的一对箱子( i , i 1 ) (i, i1)(i,i1)它们能开始交配的最早时间是max ⁡ ( a i , a i 1 ) \max(a_i, a_{i1})max(ai​,ai1​)最晚能产蛋的时间是第t − 1 t-1t−1天能贡献的新鸡蛋数量为w i max ⁡ ( 0 , ( t − 1 ) − max ⁡ ( a i , a i 1 ) 1 ) max ⁡ ( 0 , t − max ⁡ ( a i , a i 1 ) ) w_i \max\left(0,\; (t-1) - \max(a_i, a_{i1}) 1\right) \max(0,\; t - \max(a_i, a_{i1}))wi​max(0,(t−1)−max(ai​,ai1​)1)max(0,t−max(ai​,ai1​))所以答案直接就是A ∑ i 1 n − 1 max ⁡ ( 0 , t − max ⁡ ( a i , a i 1 ) ) A \sum_{i1}^{n-1} \max \big(0,\; t - \max(a_i, a_{i1}) \big)Ai1∑n−1​max(0,t−max(ai​,ai1​))时间复杂度和空间复杂度皆为O ( n ) O(n)O(n)。3. 代码usingSystem;usingSystem.Linq;classProgram{staticlongn,t;staticstring[]line;staticlong[]a;staticvoidMain(){lineConsole.ReadLine().Split();nConvert.ToInt64(line[0]);tConvert.ToInt64(line[1]);anewlong[n];lineConsole.ReadLine().Split();for(inti0;in;i){a[i]Convert.ToInt64(line[i]);}longans0;for(inti0;in-1;i){longhatchMath.Max(a[i],a[i1]);if(thatch){anst-hatch;}}Console.WriteLine(ans);}}4. 轶事思考一下如果鸡的位置允许调换呢那答案也很简单尽可能缩小相邻两只鸡的孵化时间差距就好了这样才能最大限度地避免晚孵化的鸡拖早鸟的后腿。多一波排序操作就可以了。