Codeforces-1672 C: Unequal Array
题目
题目截图
样例描述
题目大意
? 给定一个长度为
n
n
n 的数组
a
a
a。定义这个数组的相等性为满足条件
a
i
=
a
i
+
1
,
i
∈
[
1
,
n
?
1
]
a_i=a_{i+1},i\in[1,n-1]
ai?=ai+1?,i∈[1,n?1] 的
i
i
i 的数量。
? 现在可以对这个数组做一些操作，可以选择一个下标
i
∈
[
1
,
n
?
1
]
i \in [1,n-1]
i∈[1,n?1]，将
a
i
a_i
ai? 和
a
i
+
1
a_{i+1}
ai+1? 都设置为
x
x
x，问最少需要多少次操作，能够让 这个数组的相等性
≤
1
\le 1
≤1。-
题目解析
? 首先考虑一般的情况，我们假设有
a
=
[
?
X
X
X
X
?
Y
Y
Y
?
Z
Z
Z
?
?
]
a = [\cdots XXXX\cdots YYY \cdots ZZZ \cdots]
a=[?XXXX?YYY?ZZZ?]，显然这个数组是不符合相等性条件的，那么我们怎么样使用给定的方法消除里面相等的部分呢？
? 首先，我们注意到一共只有不超过
2
e
5
2e5
2e5 的数，但数值范围有
1
e
9
1e9
1e9，这意味着我们赋值的时候每次都赋值
x
x
x 为从没出现过的数就好了。然后，对于多个连续相等的情况，我们从第一段第二位开始，就要赋值
x
x
x 了，这样带来的结果是
a
=
[
?
X
A
A
X
?
Y
Y
Y
?
Z
Z
Z
?
?
]
a = [\cdots XAAX\cdots YYY \cdots ZZZ \cdots]
a=[?XAAX?YYY?ZZZ?]，根据题目要求，我们只有最后只有两个数是相等且连续出现的，但我们每次赋值，都必然会留下一个相等连续出现的数，这使得我们必须接着向后进行
a
=
[
?
X
A
B
B
?
Y
Y
Y
?
Z
Z
Z
?
?
]
a = [\cdots XABB\cdots YYY \cdots ZZZ \cdots]
a=[?XABB?YYY?ZZZ?]，看到这里，我们不难发现，按这样赋值，每次我们都可以将首次出现连续相等的位置向后移动一位，显然，当到最后一次时，
a
=
[
?
X
A
B
C
?
D
D
Z
?
?
]
a = [\cdots XABC\cdots DDZ \cdots]
a=[?XABC?DDZ?]，这样，我们就能得到题目想要的结果。这个过程中，设首次出现连续相等段的起点为 s，最后一次出现的终点为 e，那么显然这样结果就是
(
e
?
1
)
?
(
s
+
1
)
=
e
?
s
?
2
(e - 1) - (s + 1) = e - s - 2
(e?1)?(s+1)=e?s?2。
? 特别地，需要注意两个地方，一个是本就满足条件的情况（
e
d
<
s
t
ed \lt st
ed<st 对应连续段唯一且长度只有
2
2
2 或没有连续段），另一个是连续段长度为
3
3
3 时，我们只需要赋值一次，此时答案应为
1
1
1。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn], b[maxn], cnt[maxn];
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n >> a[1];
int st = 0, ed = -1;
for(int i=2; i<=n; ++i) {
cin >> a[i];
if(st == 0 && a[i] == a[i-1]) st = i;
if(a[i] == a[i-1]) ed = i - 1;
}
if(ed < st) cout << 0 << endl; else
cout << max(1, ed - st) << endl;
}
return 0;
}
