小红的数组操作时间限制1 秒空间限制1024 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一个长度为n nn的数组a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​初始所有元素都是黑色。她可以进行以下两种操作每种操作最多进行一次选择一个下标i ii花费a i × i a_i \times iai​×i的代价将a i a_iai​和a i a_iai​之前的所有元素都染成红色选择一个下标i ii花费a i × ( n − i 1 ) a_i \times (n - i 1)ai​×(n−i1)的代价将a i a_iai​和a i a_iai​之后的所有元素都染成红色。小红希望最终数组中不包含任意相同的黑色元素请你帮小红求出所需要的最小代价。输入描述第一行输入一个整数n ( 1 ≤ n ≤ 3 × 10 5 ) n\ (1 \le n \le 3 \times 10^5)n(1≤n≤3×105)代表数组的大小。第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 10 9 ) a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)a1​,a2​,…,an​(1≤ai​≤109)代表数组的元素。输出描述输出一个整数代表小红所需要的最小代价。示例示例 1输入5 1 2 3 2 1输出4说明在这个样例中其中一种合法的操作方法是选择下标4 44执行第二种操作花费2 × 2 4 2 \times 2 42×24的代价后两个数字被染红数组变为{ 1 , 2 , 3 , 2 , 1 } \{1,2,3,\color{red}{2,1}\}{1,2,3,2,1}所有黑色元素互不相同。数据范围与提示1 ≤ n ≤ 3 × 10 5 1 \le n \le 3 \times 10^51≤n≤3×1051 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109两种操作每种最多只能进行一次也可以选择不进行某种操作。解题思路本题要求通过最多一次前缀染色和最多一次后缀染色使得剩余黑色元素互不相同求最小总代价。核心在于利用双指针找出所有可能的无重复元素子段即黑色保留段并预处理前后缀的最小操作代价枚举该段即可得到全局最优解。1. 问题等价转化最终形态两种操作各最多一次因此染色区域必然是一个前缀和/或一个后缀中间留下一个连续的黑色子段可能为空。要求黑色子段内元素互不相同。操作代价前缀操作选择下标i ii1‑based染红a 1 ∼ a i a_1 \sim a_ia1​∼ai​代价a i × i a_i \times iai​×i。后缀操作选择下标i ii染红a i ∼ a n a_i \sim a_nai​∼an​代价a i × ( n − i 1 ) a_i \times (n-i1)ai​×(n−i1)。覆盖范围放宽若想覆盖前缀[ 1 , x ] [1, x][1,x]实际上可以选择任意i ≥ x i \ge xi≥x的前缀操作只需付出对应的代价。因此覆盖前缀[ 1 , x ] [1, x][1,x]的最小代价为min ⁡ i ≥ x ( a i × i ) \min_{i \ge x} (a_i \times i)mini≥x​(ai​×i)。同理覆盖后缀[ y , n ] [y, n][y,n]的最小代价为min ⁡ i ≤ y ( a i × ( n − i 1 ) ) \min_{i \le y} (a_i \times (n-i1))mini≤y​(ai​×(n−i1))。2. 预处理最小代价数组数组下标统一转换为 0‑based便于处理。pre[i]表示覆盖前缀[ 0 , i − 1 ] [0, i-1][0,i−1]的最小代价。计算方式先计算每个位置i ii作为前缀操作点的原始代价a[i] * (i1)然后从右向左取后缀最小值。即pre[i] min(原始代价[i], pre[i1])表示以位置i ii作为左端点的覆盖前缀的最小代价。suf[i]表示覆盖后缀[ i , n − 1 ] [i, n-1][i,n−1]的最小代价。计算每个位置i ii的原始代价a[i] * (n-i)然后从左向右取前缀最小值。即suf[i] min(suf[i-1], 原始代价[i])表示以位置i ii作为右端点的覆盖后缀的最小代价。特殊情况不进行前缀操作时代价为0 00可令pre[n] 0覆盖空前缀不进行后缀操作时代价为0 00令suf[-1] 0实现时注意边界处理。3. 滑动窗口枚举黑色保留段维护双指针l, i使得窗口[ l , i ] [l, i][l,i]内元素互不相同用集合st判重。枚举右端点i ii从0 00到n − 1 n-1n−1若a[i]已在集合中则不断右移左指针l ll并移除a[l]直到窗口内不再重复。将a[i]加入集合。此时窗口[ l , i ] [l, i][l,i]为满足条件的黑色保留段左边需覆盖[ 0 , l − 1 ] [0, l-1][0,l−1]右边需覆盖[ i 1 , n − 1 ] [i1, n-1][i1,n−1]。总代价为pre[l] suf[i1]。取所有窗口的最小值。注意窗口可以为空l i l ili表示全部染红此时代价为pre[0]或suf[n]实际在枚举中会被覆盖例如当l 0 , i − 1 l0, i-1l0,i−1时但双指针自然处理。4. 复杂度分析时间复杂度预处理O ( n ) O(n)O(n)双指针每个元素最多进出集合一次O ( n ) O(n)O(n)。总O ( n ) O(n)O(n)n ≤ 3 × 10 5 n \le 3\times 10^5n≤3×105完全可行。空间复杂度O ( n ) O(n)O(n)存储数组及辅助数组。总结将问题抽象为“中间保留一个无重复子段两边用最优前缀/后缀操作覆盖”通过预处理任意前后缀的最小覆盖代价结合滑动窗口枚举所有合法黑色子段即可在线性时间内求出最小总代价。代码简要说明输入与预处理读入数组a aa。构建pre数组pre[i] a[i] * (i1)再从n − 1 n-1n−1到0 00取min使pre[i]成为覆盖[ 0 , i − 1 ] [0, i-1][0,i−1]的最小代价。构建suf数组suf[i] a[i] * (n-i)再从1 11到n − 1 n-1n−1取min使suf[i]成为覆盖[ i , n − 1 ] [i, n-1][i,n−1]的最小代价。边界suf[n]视为0 00代码中用suf[i1]。滑动窗口初始化左指针l 0 l0l0集合st答案res INF。遍历右指针i ii若a[i]重复则右移l ll并删除a[l]插入a[i]用pre[l] suf[i1]更新答案。输出输出res。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;vectorlla(n);for(autox:a)cinx;vectorllpre(n1),suf(n1);for(ll i0;in;i){pre[i1]a[i]*(i1);suf[i]a[i]*(n-i);}for(ll in-1;i0;i--)pre[i]min(pre[i],pre[i1]);for(ll i1;in;i)suf[i]min(suf[i],suf[i-1]);setllst;ll resINF;ll l0;for(ll i0;in;i){while(st.count(a[i])){st.erase(a[l]);l;}st.insert(a[i]);resmin(res,pre[l]suf[i1]);}coutresendl;return0;}