本文主要是介绍HDU 1541 Stars || POJ 2352 stars || NYOJ 117 求逆序数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：其实都是求逆序数，但是NYOJ 数特别大，需要离散化一下。
解题思路：HDU || POJ 上的 stars 求左下角有多少个星星，因为是按 y 值递增排好序的,so 只要前面的点的 x 坐标小于等于当前 x 坐标的就可以了。查找时向下查找，更新时向上更新。NYOJ 那题因为数特别大，需要离散化一下（切记排序时要稳定排序），只要用下表减去查找到有几个比它小的就可以了。
代码（HDU）：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld long long int
const double PI = 3.1415926535898 ;
const double INF = 99999999 ;
const long long mod= 1000 ;
const int MX = 100005 ;
int a[MX],sum[MX] ;
int lowbit(int x)
{return x&(-x) ;
}
void add(int x) // 向上更新
{while(x<MX){a[x]++ ;x+=lowbit(x) ;}
}
int su(int x) // 求有几个在它左下方的点
{int ans=0 ;while(x>0){ans+=a[x] ;x-=lowbit(x) ;}return ans ;
}
int main()
{int x,y,n ;while(~scanf("%d",&n)){memset(a,0,sizeof(a)) ;memset(sum,0,sizeof(sum)) ;for(int i=0 ;i<n ;i++){scanf("%d%d",&x,&y) ;x++ ; // 有可能为 0sum[su(x)]++ ; // 相应的等级加 1add(x) ; // 向上更新}for(int i=0 ;i<n ;i++)printf("%d\n",sum[i]) ;}return 0 ;
}
代码（NYOJ）：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld long long int
const double PI = 3.1415926535898 ;
const double INF = 99999999 ;
const long long mod= 1000 ;
const int MX = 1000005 ;
int n ;
int a[MX],c[MX] ;
struct node
{int x,y ;
}T[MX] ;
bool cmp(node a,node b)
{return a.x < b.x ;
}
int lowbit(int x)
{return x&(-x) ;
}
void add(int x)
{while(x<=n){c[x]++ ;x+=lowbit(x) ;}
}
int su(int x)
{int ans=0 ;while(x>0){ans+=c[x] ;x-=lowbit(x) ;}return ans ;
}
int main()
{int Tx ;scanf("%d",&Tx) ;while(Tx--){scanf("%d",&n) ;memset(a,0,sizeof(a)) ;memset(c,0,sizeof(c)) ;for(int i=1 ;i<=n ;i++){scanf("%d",&T[i].x) ;T[i].y=i ;}stable_sort(T+1,T+n+1,cmp) ;// 切记稳定排序for(int i=1 ;i<=n ;i++) // 离散化a[T[i].y]=i ;lld sum=0 ;for(int i=1 ;i<=n ;i++){add(a[i]) ;sum+=i-su(a[i]) ;}printf("%lld\n",sum) ;}return 0 ;
}
这篇关于HDU 1541 Stars || POJ 2352 stars || NYOJ 117 求逆序数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
