首页 > 代码库 > 51nod1107(逆序对数&归并排序)

51nod1107(逆序对数&归并排序)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107

 

题意:中文题诶~

 

思路:通过题意可以发现对于两点p1(x1, y1),p2(x2, y2), 若x1<x2&&y1>y2则线段p1p2满足要求,那么显然可以先按x值排下序,对应y序列的逆序对数目即为答案;

注意:对于x1==x2&&y1>y2的情况是不满足题意的,可以通过重载排序去除x值相等的情况下的y逆序对;

 

代码:

技术分享
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #define ll long long
 5 using namespace std;
 6 
 7 const int MAXN=5e4+10;
 8 struct node{
 9     int first;
10     int second;
11 }p[MAXN];
12 ll ans=0;
13 
14 bool cmp(node a, node b){
15     if(a.first==b.first) return a.second<b.second;
16     return a.first<b.first;
17 }
18 
19 void teger_sort(int* a, int* t, int x, int y){
20     if(y-x>1){  //**递归至单个元素为一组
21         int m=(y+x)>>1;
22         int p=x, q=m, i=x;
23         teger_sort(a, t, x, m);  //***左递归
24         teger_sort(a, t, m, y);  //***右递归
25         while(p<m||q<y){   //**合并
26             if(q>=y||(p<m&&a[p]<=a[q])){
27                 t[i++]=a[p++];  //**将左边元素复制到临时数组
28             }else{
29                 t[i++]=a[q++]; //**将右边元素复制到临时数组
30                 ans+=m-p; //**累计逆序对的数目
31             }
32         }
33         for(int i=x; i<y; i++){ //**将临时数组里已排序的元素还原到原数组
34             a[i]=t[i];
35         }
36     }
37 }
38 
39 int main(void){
40     int n, a[MAXN], t[MAXN];
41     scanf("%d", &n);
42     for(int i=0; i<n; i++){
43         scanf("%d%d", &p[i].first, &p[i].second);
44     }
45     sort(p, p+n, cmp);
46     for(int i=0; i<n; i++){
47         a[i]=p[i].second;
48     }
49     teger_sort(a, t, 0, n);
50     printf("%lld\n", ans);
51     return 0;
52 }
View Code

 

51nod1107(逆序对数&归并排序)