小红的数组操作【牛客tracker 每日一题】

小红的数组操作

时间限制：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−i+1)的代价，将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×2=4的代价，后两个数字被染红，数组变为{ 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×105
• 1 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109
• 两种操作每种最多只能进行一次，也可以选择不进行某种操作。

解题思路

本题要求通过最多一次前缀染色和最多一次后缀染色，使得剩余黑色元素互不相同，求最小总代价。核心在于利用双指针找出所有可能的无重复元素子段（即黑色保留段），并预处理前后缀的最小操作代价，枚举该段即可得到全局最优解。

1. 问题等价转化

• 最终形态：两种操作各最多一次，因此染色区域必然是一个前缀和/或一个后缀，中间留下一个连续的黑色子段（可能为空）。要求黑色子段内元素互不相同。
• 操作代价：
  • 前缀操作选择下标i ii（1‑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-i+1)ai​×(n−i+1)。
• 覆盖范围放宽：若想覆盖前缀[ 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-i+1))mini≤y​(ai​×(n−i+1))。

2. 预处理最小代价数组

• 数组下标统一转换为 0‑based，便于处理。
• pre[i]：表示覆盖前缀[ 0 , i − 1 ] [0, i-1][0,i−1]的最小代价。计算方式：先计算每个位置i ii作为前缀操作点的原始代价a[i] * (i+1)，然后从右向左取后缀最小值。即pre[i] = min(原始代价[i], pre[i+1])，表示以位置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 ] [i+1, n-1][i+1,n−1]。总代价为pre[l] + suf[i+1]。取所有窗口的最小值。
• 注意窗口可以为空（l > i l > il>i），表示全部染红，此时代价为pre[0]或suf[n]，实际在枚举中会被覆盖（例如当l = 0 , i = − 1 l=0, i=-1l=0,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)存储数组及辅助数组。

总结

将问题抽象为“中间保留一个无重复子段，两边用最优前缀/后缀操作覆盖”，通过预处理任意前后缀的最小覆盖代价，结合滑动窗口枚举所有合法黑色子段，即可在线性时间内求出最小总代价。

代码简要说明

1. 输入与预处理：
   • 读入数组a aa。
   • 构建pre数组：pre[i] = a[i] * (i+1)，再从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[i+1]）。
2. 滑动窗口：
   • 初始化左指针l = 0 l=0l=0，集合st，答案res = INF。
   • 遍历右指针i ii：若a[i]重复则右移l ll并删除a[l]；插入a[i]；用pre[l] + suf[i+1]更新答案。
3. 输出：输出res。

代码内容

#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;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;vector<ll>a(n);for(auto&x:a)cin>>x;vector<ll>pre(n+1),suf(n+1);for(ll i=0;i<n;i++){pre[i+1]=a[i]*(i+1);suf[i]=a[i]*(n-i);}for(ll i=n-1;i>0;i--)pre[i]=min(pre[i],pre[i+1]);for(ll i=1;i<n;i++)suf[i]=min(suf[i],suf[i-1]);set<ll>st;ll res=INF;ll l=0;for(ll i=0;i<n;i++){while(st.count(a[i])){st.erase(a[l]);l++;}st.insert(a[i]);res=min(res,pre[l]+suf[i+1]);}cout<<res<<endl;return0;}