Question Name:Kevin doesn’t like his array

#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
const int INF = 1000000000;
const int MAX = 100007;
const int MAX2 = 1000000;
const int MAXD = 20;
const int BASE = 1000000007;
const int MOD = 1000000007;
int b[MAX];
int a[MAX];
int c[MAX];
int main()
{
    //freopen("in.txt" , "r" , stdin);
    int n;
    cin >> n;
    vector<int> a(n);
    int B = 0;
    int C = 0;
    int S = 0;
    FOR(i,0,n)
    {
        scanf("%d" , &a[i]);
        b[a[i]]++;
        B = max(B , b[a[i]]);
        if (i && a[i] == a[i - 1])
        {
            ++S;
            c[a[i]]++;
            C = max(C , c[a[i]]);
        }
    }
    if (B > (n + 1) / 2)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << max((S + 1) / 2 , C) << endl;
    }
	return 0;
}
  • Problem Description
    Kevin has an array A of N integers, but he doesn’t like it – he only likes an array if all its neighboring elements are different (e.g. he likes the array [2,4,2,5,3,2,4], but not [1,2,3,3,4]).

    Kevin can reverse any contiguous subarray of his array any number of times. For example, if he has the array [2,4,2,5,3,2,4] and reverses the subarray from 2nd to 5th element, he will obtain the array [2,3,5,2,4,2,4].

    Now, Kevin wants to know the minimum number of reversals necessary to transform his array into an array he likes – if it’s possible.

    Input format:

    The first line of the input will contain an integer N. The second line will contain N space-separated integers – the elements of A.

    Output format:

    If it’s impossible to transform Kevin’s array into an array he likes, print “-1” (without the quotes). Otherwise, print one number – the minimum number of reversals necessary.

    Constraints:

    1 <= N <= 10^5
    1 <= Ai <= 10^5
    N <= 5 in test data worth 15% of all points
    N <= 10^3 in test data worth 40% of all points
  • Test Case 1
    Input (stdin)7
    1 3 2 2 4 4 4
    Expected Output2
  • Test Case 2
    Input (stdin)5
    42343 42343 99122 7722 7722
    Expected Output1

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro