codeforces

好久没干这事了相关链接灵茶の试炼Spectral::Cup 2026 Round 3 (Codeforces Round 1110, Div. 1 Div. 2)题目描述输入T ( ≤ 10 4 ) T(\le 10^4)T(≤104)表示T TT组数据。所有数据的n nn之和≤ 2 × 10 5 \le 2\times10^5≤2×105。每组数据输入n ( 1 ≤ n ≤ 2 × 10 5 ) n(1\le n\le 2\times10^5)n(1≤n≤2×105)c ( 0 ≤ c ≤ 10 9 ) c(0\le c\le10^9)c(0≤c≤109)和长为n nn的数组a ( − 10 9 ≤ a [ i ] ≤ 10 9 ) a(-10^9\le a[i]\le10^9)a(−109≤a[i]≤109)。你可以执行如下两种操作任意次直到a aa变成空的。每次操作后得分减少c cc。删除a aa中的一个数x xx把得分增加x xx。删除a aa中的相邻元素x xx和y yy把得分增加( max ⁡ ( x , y ) ) (\max(x,y))(max(x,y))。该操作要求a aa至少有两个数。输出总得分的最大值。核心想法把小于c cc的数「顺带」删除。每次删1 ∼ 2 1\sim21∼2个数所以最少操作( c e i l ) ( n / 2 ) \mathrm{(\mathrm{ceil})}(n/2)(ceil)(n/2)次最多操作n nn次。设( c n t ) \mathrm{(\mathrm{cnt})}(cnt)为a aa中≥ c \ge c≥c的数的个数。如果( c n t ) ≥ ( c e i l ) ( n / 2 ) \mathrm{(\mathrm{cnt})} \ge \mathrm{(\mathrm{ceil})}(n/2)(cnt)≥(ceil)(n/2)那么取前( c n t ) \mathrm{(\mathrm{cnt})}(cnt)大的数操作( c n t ) \mathrm{(\mathrm{cnt})}(cnt)次。否则必须取前( c e i l ) ( n / 2 ) \mathrm{(\mathrm{ceil})}(n/2)(ceil)(n/2)大的数操作( c e i l ) ( n / 2 ) \mathrm{(\mathrm{ceil})}(n/2)(ceil)(n/2)次。注意「相邻」的条件是多余的当要顺带删除的数和要加到答案的数的个数一样时总是存在一对相邻元素其中一个是要顺带删除的数另一个是要加到答案的数。补充说明( c e i l ) \mathrm{(\mathrm{ceil})}(ceil)代表向上取整。操作代价每进行1次操作总得分− c -c−c。操作1删1个得分( x ) (x)(x)操作2删相邻2个得分 ( max ⁡ ( x , y ) ) (\max(x,y))(max(x,y))。参考代码#includebits/stdc.husingnamespacestd;usinglllonglong;voidyy(){intn,c;cinnc;vectorinta(n);for(intx:a)cinx;sort(a.rbegin(),a.rend());intcnt0;ll ans0;for(autox:a)cnt(xc);cntmax(cnt,(n1)/2);for(inti0;icnt;i)ansa[i]-c;coutans\n;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int_;cin_;while(_--)yy();return0;}