정렬 및 예제 병합
기 존 서열 의 하위 서열 을 합쳐서 완전히 질서 있 는 서열 을 얻는다.즉, 모든 하위 서열 을 질서 있 게 한 다음 에 하위 서열 을 질서 있 게 하 는 것 이다.
두 개의 질서 표를 하나의 질서 표 로 합치 면 2 번 병합 이 라 고 합 니 다.병합 정렬 은 안정 적 인 정렬 방법 이다.
용도:
정렬 속도:
(속 도 는 빠 른 정렬 에 이 어 안정 적 인 정렬 알고리즘 으로 전체 무질서 에 사용 되 지만 각 하위 항목 이 상대 적 으로 질서 있 는 수열)
역순 대수 구하 기:
구체 적 인 사 고 는 병합 과정 에서 각 동네 간 의 역순 대 수 를 계산 하여 큰 구간 의 역순 대 수 를 계산 하 는 것 이다 (나무 모양 배열 로 도 풀 수 있다).
#include
const int MAXN=200005;
int n, a[MAXN], temp[MAXN];
long long ans;
void count(int l, int r)
{
if(r == l) return ;//
int m = (l + r) >> 1;//（l+r） 1 ， （l+r）/2
count(l, m);
count(m + 1, r);//
int i = l, j = m + 1, k = l;
while(j <= r || i <= m) {
if(j > r || (i <= m && a[i] < a[j]))
temp[k++] = a[i++];
else
temp[k++] = a[j++], ans += m - i + 1; }
for(i = l; i <= r; i++)
a[i] = temp[i];}
int main()
{ scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]); count(1, n);//
printf("%lld", ans);//
return 0;
} 예제: HDU 4911 Inversion 역순 수 쌍
https://blog.csdn.net/crescent__moon/article/details/38424829
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
