文章目录
- 题目描述
- 输入格式
- 输出格式
- 样例输入1
- 样例输出1
- 样例输入2
- 样例输出2
- 样例输入3
- 样例输出3
- 提交链接
- 提示
- 解析
- 参考代码
题目描述
让我们把一个数组 a a a 称作美丽的数组,如果你能通过任意次数(可能是零)的下面操作使数组中的所有元素都相同的话:
- 选择一个索引 i ( 2 ≤ i ≤ ∣ a ∣ − 1 , a i − 1 = a i + 1 ) i(2 \leq i \leq |a|-1,a_{i-1}=a_{i+1}) i(2≤i≤∣a∣−1,ai−1=ai+1) ,然后将 a i a_i ai 替换为 a i − 1 a_{i-1} ai−1 。
给你一个漂亮的数组 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,要使数组不再美丽,至少要删除多少个元素?禁止交换元素。如果不可能这样做,那么输出 − 1 -1 −1。
输入格式
第一行包含一个整数 n ( 1 ≤ n ≤ 3 ∗ 1 0 5 ) n(1 \leq n \leq 3 * 10^5) n(1≤n≤3∗105)。
第二行包含 n n n 个整数 a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ n ) a_1,a_2,...,a_n(1 \leq a_i \leq n) a1,a2,...,an(1≤ai≤n)。
输出格式
输出一个整数–为了使数组
a
a
a 不再美丽,你必须从数组
a
a
a 中移除的最小元素数。
如果不可能,那么输出 -1。
样例输入1
3
2 2 2
样例输出1
-1
样例输入2
5
1 2 1 2 1
样例输出2
1
样例输入3
7
3 3 3 5 3 3 3
样例输出3
3
提交链接
https://hydro.ac/d/lp728/p/16
提示
保证输入的 a a a 数组为美丽的数组。
样例解释:
在第一个测试案例中,不可能通过修改数组的方式使其不再美丽。无论我们从数组中删除多少数字,由相同数字组成的数组都会保持美丽。
在第二个测试案例中,你可以删除索引 5 5 5 中的数字。这样得到的数组将是 [ 1 , 2 , 1 , 2 ] [1,2,1,2] [1,2,1,2] 让我们看看它是否美丽。有两种操作可供选择:
- 选择 i = 2 i=2 i=2:数组变为 [ 1 , 1 , 1 , 2 ] [1,1,1,2] [1,1,1,2]。不能再对其进行其他操作,而且数字也不尽相同。
- 选择 i = 3 i=3 i=3:数组变为 [ 1 , 2 , 2 , 2 , ] [1,2,2,2,] [1,2,2,2,]。也不能对其进行更多的运算,数字仍然不完全相同。
因此,数组 [ 1 , 2 , 1 , 2 ] [1,2,1,2] [1,2,1,2] 并不美观。
在第三个测试用例中,可以删除前三个元素。这样得到的数组 [ 5 , 3 , 3 , 3 ] [5,3,3,3] [5,3,3,3] 并不美观。
解析
数组 a a a 为美丽数组,则一定能是所有的元素都相同,即 a [ i ] = x a[i]=x a[i]=x。
我们在变换一致的过程中,能选择的下标的范围为 2 ≤ i ≤ ∣ a ∣ − 1 2 \leq i \leq |a|-1 2≤i≤∣a∣−1 ,是无法对 a [ 1 ] a[1] a[1] 或 a [ n ] a[n] a[n] 来进行操作的。所以我们可以得出 x x x 一定是等于 a [ 1 ] a[1] a[1]。
如何让数组不再美丽,可以的操作有:
- 删除等于 a [ 1 ] a[1] a[1] 的整个数字前缀
- 删除等于 a [ 1 ] a[1] a[1] 的整个数字后缀
- 选择两个不等于 a [ 1 ] a[1] a[1] 的数字,删除它们之间的所有数字,使这两个数字相邻。
答案变为:找出等于 a [ 1 ] a[1] a[1] 的最短数块。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 9;
int t , n , a[maxn];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int idx = a[1];
int mi = 9999999 , len = 0;
for(int i = 1; i <= n; i++)
{
if(a[i] == idx)
len++;
else
{
mi = min(mi , len);
len = 0;
}
}
mi = min(mi , len);
if(mi != n)
cout << mi << endl;
else
cout << -1 << endl;
return 0;
}