CF??Codeforces Global Round 20? C题
You are given an array?aa?of length?nn. We define the?equality?of the array as the number of indices?1≤i≤n?11≤i≤n?1?such that?ai=ai+1ai=ai+1. We are allowed to do the following operation:
- Select two integers?ii?and?xx?such that?1≤i≤n?11≤i≤n?1?and?1≤x≤1091≤x≤109. Then, set?aiai?and?ai+1ai+1?to be equal to?xx.
Find the minimum number of operations needed such that the equality of the array is less than or equal to?11.
Input
Each test contains multiple test cases. The first line contains a single integer?tt?(1≤t≤1041≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer?nn?(2≤n≤2?1052≤n≤2?105) — the length of array?aa.
The second line of each test case contains?nn?integers?a1,a2,…,ana1,a2,…,an?(1≤ai≤1091≤ai≤109) — elements of the array.
It is guaranteed that the sum of?nn?over all test cases does not exceed?2?1052?105
Output
For each test case, print the minimum number of operations needed.
Example
input
Copy
4 5 1 1 1 1 1 5 2 1 1 1 2 6 1 1 2 3 3 4 6 1 2 1 4 5 4
output
Copy
2 1 2 0
Note
In the first test case, we can select?i=2i=2?and?x=2x=2?to form?[1,2,2,1,1][1,2,2,1,1]. Then, we can select?i=3i=3?and?x=3x=3?to form?[1,2,3,3,1][1,2,3,3,1].
In the second test case, we can select?i=3i=3?and?x=100x=100?to form?[2,1,100,100,2][2,1,100,100,2].
思路：这个题是让挨着的相同的最多有1个。一开始没有好好看样例，把思路搞错了，以样例 1 1 2 3 3 4 为例，当出现相同的时候我们去改后一个，这样才能使两者不同，然后会发现把前一个相同的改过了，然后后面又出现一对相同的（“笑了”），那么我们改到什么时候才能停止呢？是不是要改到原数组的最后一对相同的倒数第二个，然后是从谁开始的呢？当然是原数组的第一对的第二个，那么我们我们是不是只要将这两个端点记录下，相减即可。
完整代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=2e5+10;
int a[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int minn=1e9,maxx=0;
for(int i=2;i<=n;i++)
{
if(a[i]==a[i-1])
{
minn=min(minn,i);
maxx=max(maxx,i);
}
}
if(maxx-minn<1)cout<<"0"<<endl;
else cout<<max(maxx-minn-1,1ll)<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
