codechef Little Elephant and Permutations 문제 해결
3561 단어 code
He calls a permutation A good, if the number of its inversions is equal to the number of its local inversions. The number of inversions is equal to the number of pairs of integers (i; j) such that 1 ≤ i < j ≤ N and A[i] > A[j], and the number of local inversions is the number of integers i such that 1 ≤ i < N and A[i] > A[i+1].
The Little Elephant has several such permutations. Help him to find for each permutation whether it is good or not. Print YES for a corresponding test case if it is good and NO otherwise.
Input
The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of a permutation. The next line contains N space separated integers A[1], A[2], ..., A[N].
Output
For each test case output a single line containing the answer for the corresponding test case. It should beYES if the corresponding permutation is good and NO otherwise.
Constraints
1 ≤ T ≤ 474
1 ≤ N ≤ 100
It is guaranteed that the sequence A[1], A[2], ..., A[N] is a permutation of numbers 1, 2, ..., N.
Example
Input:
4
1
1
2
2 1
3
3 2 1
4
1 3 2 4
Output:
YES
YES
NO
YES
요약하면 다음과 같습니다.
전역 역순수 = 기포 정렬 교환 데이터 교환 횟수
이 문제는 데이터량이 적어 폭력법으로 계산할 수 있다.
그러나 이 시간 효율은 O(N*N)이므로 O(nlgn)로 줄이려면mergersort를 사용해야 한다.
다음 유형에는 폭력법과 메르지 소트 방법이 모두 포함되어 있다.
#pragma once
#include <stdio.h>
#include <stdlib.h>
class LittleElephantAndPermutations
{
int localInverse(const int *A, const int n)
{
int ans = 0;
for (int i = 1; i < n; i++)
{
if (A[i-1] > A[i]) ans++;
}
return ans;
}
int globalInverse(const int *A, const int n)
{
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
if (A[i] > A[j]) ans++;
}
}
return ans;
}
int *mergeArr(int *left, int L, int *right, int R, int &c)
{
int *lr = new int[L+R];
int i = 0, j = 0, k = 0;
while (i < L && j < R)
{
if (left[i] <= right[j])
{
lr[k++] = left[i++];
}
else
{
lr[k++] = right[j++];
c += L-i;
}
}
while (i < L)
{
lr[k++] = left[i++];
}
while (j < R)
{
lr[k++] = right[j++];
}
return lr;
}
int biGlobalInverse(int *&A, const int n)
{
if (n <= 1) return 0;
int mid = (n-1) >> 1;// n-1
int *left = new int[n];
int *right = new int[n];
int L = 0, R = 0;
for ( ; L <= mid; L++)
{
left[L] = A[L];
}
for (int i = mid+1; i < n; i++, R++)
{
right[R] = A[i];
}
delete [] A;
int c1 = biGlobalInverse(left, L);
int c2 = biGlobalInverse(right, R);
int c = 0;
A = mergeArr(left, L, right, R, c);
delete left;
delete right;
return c1+c2+c;
}
public:
void run()
{
int T = 0, N = 0;
scanf("%d", &T);
while (T--)
{
scanf("%d", &N);
int *A = new int[N];
for (int i = 0; i < N; i++)
{
scanf("%d", &A[i]);
}
int loc = localInverse(A, N);
int glo = biGlobalInverse(A, N);
if (loc == glo) puts("YES");
else puts("NO");
}
}
};
int littleElephantAndPermutations()
{
LittleElephantAndPermutations le;
le.run();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.