题目内容
原题链接
给定一个长度为
n
n
n 的整数数组
a
a
a ,
a
i
∈
[
0
,
1
]
a_i\in [0,1]
ai∈[0,1] 。
对于一个子数组
a
l
,
a
l
+
1
,
⋯
,
a
r
a_l,a_{l+1},\cdots ,a_r
al,al+1,⋯,ar ,一次修改操作意味着将
a
i
=
0
a_i=0
ai=0 修改为
a
i
=
1
a_i=1
ai=1 ,将
a
i
=
1
a_i=1
ai=1 修改为
a
i
=
0
a_i=0
ai=0 。
问修改至多一次(可以不修改),可以修改出多少种数组和不同的数组
a
a
a 。
数据范围
-
1
≤
n
≤
3
×
1
0
5
1\leq n\leq 3\times 10^5
1≤n≤3×105
-
0
≤
a
i
≤
1
0\leq a_i\leq 1
0≤ai≤1
题解
暴力
枚举每个子数组,计算每个子数组翻转后可能有多少个不同的值。用
s
e
t
set
set 去重即可。
时间复杂度:
O
(
n
2
log
n
)
O(n^2\log n)
O(n2logn)
正解
这里我们考虑一个问题,翻转后的值有多少种情况,如果是全
0
0
0 ,则可以翻转成
1
1
1 个
1
1
1 ,
2
2
2 个
1
1
1 ,
3
3
3 个
1
1
1 一直到
n
n
n 个
1
1
1 ,那么就是
n
n
n 种情况。
对于我们能将值减少
k
k
k 的子数组
s
u
b
sub
sub ,必能在
s
u
b
sub
sub 中选出一个子数组,使得数组的总和减少
k
−
1
k-1
k−1 ,以此类推,从减少
k
k
k 到减少
1
1
1 都可以做到。
问题转换为求可以减少最多的次数,这对应子数组中
1
1
1 的数量减去
0
0
0 的数量的最大值
u
p
up
up。
我们还需要求可以增加最多的次数,这对应子数组中
0
0
0 的数量减去
1
1
1 的数量的最大值
d
o
w
n
down
down。
最后,我们还可以选择不修改,即值不变。
所以答案为
u
p
+
d
o
w
n
+
1
up+down+1
up+down+1 。
时间复杂度:
O
(
n
)
O(n)
O(n)
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
// 找到一个 1 减 0 数量最多的数组和 0 减 1 最多的数组
vector<int> cnt(2, 0);
auto gao = [&](bool is_reverse = false) {
int res = 0;
int cur = 0;
for (int i = 0; i < n; ++i) {
if (!is_reverse) {
if (a[i] == 1) cur += 1;
else cur -= 1;
} else {
if (a[i] == 1) cur -= 1;
else cur += 1;
}
res = max(res, cur);
if (cur < 0) cur = 0;
}
return res;
};
cout << gao() + gao(true) + 1 << "\n";
return 0;
}