网硕互联帮助中心小红的数组操作
时间限制：1 秒 空间限制：1024 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
小红拿到了一个长度为
n
n
n 的数组
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \\dots, a_n
a1,a2,…,an，初始所有元素都是黑色。她可以进行以下两种操作，每种操作最多进行一次：
- 选择一个下标
i
i
i，花费a
i
×
i
a_i \\times i
ai×i 的代价，将a
i
a_i
ai 和a
i
a_i
ai 之前的所有元素都染成红色； - 选择一个下标
i
i
i，花费a
i
×
(
n
−
i
+
1
)
a_i \\times (n – i + 1)
ai×(n−i+1) 的代价，将a
i
a_i
ai 和a
i
a_i
ai 之后的所有元素都染成红色。
小红希望最终数组中不包含任意相同的黑色元素，请你帮小红求出所需要的最小代价。
输入描述
第一行输入一个整数
n
(
1
≤
n
≤
3
×
10
5
)
n\\ (1 \\le n \\le 3 \\times 10^5)
n (1≤n≤3×105)，代表数组的大小。
第二行输入
n
n
n 个整数
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
4
4 执行第二种操作，花费
2
×
2
=
4
2 \\times 2 = 4
2×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^5
1≤n≤3×105 -
1
≤
a
i
≤
10
9
1 \\le a_i \\le 10^9
1≤ai≤109 - 两种操作每种最多只能进行一次，也可以选择不进行某种操作。
解题思路
本题要求通过最多一次前缀染色和最多一次后缀染色，使得剩余黑色元素互不相同，求最小总代价。核心在于利用双指针找出所有可能的无重复元素子段（即黑色保留段），并预处理前后缀的最小操作代价，枚举该段即可得到全局最优解。
1. 问题等价转化
- 最终形态：两种操作各最多一次，因此染色区域必然是一个前缀和/或一个后缀，中间留下一个连续的黑色子段（可能为空）。要求黑色子段内元素互不相同。
- 操作代价：
- 前缀操作选择下标
i
i
i（1‑based），染红a
1
∼
a
i
a_1 \\sim a_i
a1∼ai，代价a
i
×
i
a_i \\times i
ai×i。 - 后缀操作选择下标
i
i
i，染红a
i
∼
a
n
a_i \\sim a_n
ai∼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 x
i≥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
i
i 作为前缀操作点的原始代价 a[i] * (i+1)，然后从右向左取后缀最小值。即 pre[i] = min(原始代价[i], pre[i+1])，表示以位置i
i
i 作为左端点的覆盖前缀的最小代价。 - suf[i]：表示覆盖后缀
[
i
,
n
−
1
]
[i, n-1]
[i,n−1] 的最小代价。计算每个位置i
i
i 的原始代价 a[i] * (n-i)，然后从左向右取前缀最小值。即 suf[i] = min(suf[i-1], 原始代价[i])，表示以位置i
i
i 作为右端点的覆盖后缀的最小代价。 - 特殊情况：不进行前缀操作时代价为
0
0
0，可令 pre[n] = 0（覆盖空前缀）；不进行后缀操作时代价为0
0
0，令 suf[-1] = 0，实现时注意边界处理。
3. 滑动窗口枚举黑色保留段
- 维护双指针 l, i，使得窗口
[
l
,
i
]
[l, i]
[l,i] 内元素互不相同（用集合 st 判重）。枚举右端点i
i
i 从0
0
0 到n
−
1
n-1
n−1：- 若 a[i] 已在集合中，则不断右移左指针
l
l
l，并移除 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]。取所有窗口的最小值。
- 若 a[i] 已在集合中，则不断右移左指针
- 注意窗口可以为空（
l
>
i
l > i
l>i），表示全部染红，此时代价为 pre[0] 或 suf[n]，实际在枚举中会被覆盖（例如当l
=
0
,
i
=
−
1
l=0, i=-1
l=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^5
n≤3×105 完全可行。 - 空间复杂度：
O
(
n
)
O(n)
O(n) 存储数组及辅助数组。
总结
将问题抽象为“中间保留一个无重复子段，两边用最优前缀/后缀操作覆盖”，通过预处理任意前后缀的最小覆盖代价，结合滑动窗口枚举所有合法黑色子段，即可在线性时间内求出最小总代价。
代码简要说明
- 读入数组
a
a
a。 - 构建 pre 数组：pre[i] = a[i] * (i+1)，再从
n
−
1
n-1
n−1 到0
0
0 取 min，使 pre[i] 成为覆盖[
0
,
i
−
1
]
[0, i-1]
[0,i−1] 的最小代价。 - 构建 suf 数组：suf[i] = a[i] * (n-i)，再从
1
1
1 到n
−
1
n-1
n−1 取 min，使 suf[i] 成为覆盖[
i
,
n
−
1
]
[i, n-1]
[i,n−1] 的最小代价。边界 suf[n] 视为0
0
0（代码中用 suf[i+1]）。
- 初始化左指针
l
=
0
l=0
l=0，集合 st，答案 res = INF。 - 遍历右指针
i
i
i：若 a[i] 重复则右移l
l
l 并删除 a[l]；插入 a[i]；用 pre[l] + suf[i+1] 更新答案。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
int main()
{
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;
return 0;
}
评论前必须登录！
注册