NYOJ - 역순 수 구하 기 (병합 정렬)
1983 단어 데이터 구조
시간 제한:
2000 ms | 메모리 제한:
65535 KB
난이도:
5
묘사 하 다.
한 배열 에서 한 쌍 의 앞 뒤 위치 가 크기 순서 와 반대 된다 면 앞의 수가 뒤의 수 보다 크 면 역순 이 라 고 부른다.하나의 배열 에서 역순 의 총 수 를 이 배열 의 역순 수 라 고 한다.
이제 N 개의 요소 의 서열 을 드 리 겠 습 니 다. 역순 수가 얼마 인지 판단 해 보 세 요.
예 를 들 어 1, 3, 2 의 역순 수 는 1 이다.
입력
첫 번 째 줄 에 테스트 데 이 터 를 나타 내 는 정수 T 를 입력 하 십시오 (1 < = T < = 5)
각 조 의 테스트 데이터 의 각 줄 은 하나의 정수 N 으로 수열 에 모두 N 개의 요소 가 있다 는 것 을 나타 낸다 (2 '= N' = 1000000).
다음 줄 에는 모두 N 개의 정수 Ai (0 < = Ai < 100000000) 가 있 는데 수열 의 모든 요 소 를 나타 낸다.
데 이 터 는 여러 그룹의 테스트 데이터 중에서 10 만 개 이상 의 테스트 데 이 터 는 최대 한 그룹 에 불과 하 다.
출력
이 수열 의 역순 수 를 출력 합 니 다.
샘플 입력
2
2
1 1
3
1 3 2샘플 출력
0
1/*
* ( ) ，
* ， ，
* ， ，
* ， ， 。 ， 。
*
*/
#include
#define max 1000001
long long a[max],b[max];
long long count;
void Merge(long long a[], int start, int mid , int end) //
{
int i = start,j = mid + 1,k = start;
while(i <= mid&&j <= end)
{
if(a[i] <= a[j])
{
b[k++] = a[i++];
}
else
{
count += j - k;
b[k++] = a[j++];
}
}
while(i <= mid)
{
b[k++] = a[i++];
}
while(j <= end)
{
b[k++] = a[j++];
}
for(int i = start; i <= end; i++)
{
a[i] = b[i];
}
}
void MergeSort(long long a[], int start, int end) //
{
if(start < end)
{
int mid = (start + end)/2;
MergeSort(a,start,mid); //
MergeSort(a,mid+1,end); //
Merge(a,start,mid,end); //
}
}
int main(int argc, char const *argv[])
{
int n,m;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
count = 0;
for(int i = 0; i < m; i++)
{
scanf("%d",a+i);
}
MergeSort(a,0,m-1);
printf("%lld
",count);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
