This article has participated in the “Newcomer Creation Ceremony” activity, and started the road of digging gold creation together

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is the question of the day from code source Div2 on March 27th.

Daimayuan Online Judge

I give you an array A with n elements. You can do this as many times as you want.

Merc −1≤ L ≤ L +2⋅k−1≤ N1 ≤ L ≤ L +2⋅k−1≤n, k≥1k≥1, for each I between 0 and k-1 (inclusive), assign the values al+k+ I to Al + I.

For example, if a=[2,1,3,4,5,3] and then select l=1 and k=2, apply this operation and the array will become a=[3,4,3,4,5,3].

Find the minimum operand (possibly zero) needed to make all elements in the array equal.

Input format

The input consists of multiple test cases. The first line contains an integer t (1≤ T ≤2⋅104) — the number of test cases. The test cases are described below.

The first line of each test case contains an integer N (1≤n≤2⋅10^5) — the length of the array.

The second line of each test case contains n integers A1, A2… ,an (1≤ AI ≤n) — element A of the array.

The output format

Print t lines, each containing the answer to the corresponding test case — the minimum operand required to make all elements in the array equal with the given operation.

The sample input

5. 4. 4Copy the code

Sample output

0, 1, 1, 2, 0Copy the code

The data size

12. Ensure that the sum of n for all test cases does not exceed 2⋅10^5.

prompt

In the first test, all elements are equal, so no action is required.

In the second test, you can apply one operation, k=1, l=1, set a1:=a2, and with one operation, the array becomes [1,1].

In the third test, you can apply an operation, k=1, l=4, set A4 :=a5, and the array becomes [4,4,4,4].

In the fourth test, you can apply one operation, k=1, l=3, and set a3:=a4, and the array becomes [4,2,3,3]. Then you can apply another operation, k=2, l=1, and set a1:=a3, a2:=a4, and the array becomes [3,3,3].

In the fifth test, there is only one element, so no action is required.

Problem analysis

Maybe it’s a little confusing, but we can assign the next interval to the next interval, k positions apart, and then we have to change the whole array to be the same.

So the first thing we can see is, in order to make the array the same, we have to make the entire array the same as the last one, because we can only change the previous one with the last one, so in order to make the array the same, we have to make the entire array the same as the last one.

We will begin to traverse from behind, the number of records all have the same number and the last, as ans, in the process, once encountered and the last one is not the same, we can directly change this number into the same revision number + +, but the change is too much trouble, we can directly to the back of the ans the same number of ans number assigned to the front So there are ans* 2 positions in the entire array that are the same number. Finally output the number of changes on the line.

AC code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 110;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int>v(n);
        for (int i = n-1; i >=0 ; i--)
            cin >> v[i];
        int num = v[0], res = 0, ans = 1;
        while (ans < n)
        {
            if (v[ans] == num)ans++;
            else
            {
                res++;
                ans *= 2;
            }
        }
        
        cout << res << endl;
    }
    return 0;
}

Copy the code