首页 > 代码库 > hzwer与逆序对
hzwer与逆序对
codevs——4163 hzwer与逆序对
貌似这个题和上个题是一样的（(⊙o⊙)…）
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
hzwer在研究逆序对。
对于数列{a}，如果有序数对(I,j)满足：i<j,a[i]>a[j]，则(i,j)是一对逆序对。
给定一个数列{a}，求逆序对个数。
输入数据较大，请使用scanf代替cin读入。
*为防卡评测，时限调低至1s
输入描述 Input Description
第一行一个数n,表示{a}有n个元素。
接下来n个数，描述{a}。
输出描述 Output Description
一个数，表示逆序对个数。
样例输入 Sample Input
5
3 1 5 2 4
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于10%数据，1<=n<=100.
对于20%数据，1<=n<=10000.
对于30%数据，1<=n<=100000.
对于100%数据，1<=n<=1000000,1<=a[i]<=10^8.
tips:我没有想故意卡你们时限。一点这样的意思都没有。你们不要听风就是雨……
比赛已结束 详细解析见题解
代码：
好像。。。。
这是个什么鬼？？？！！！
唉，下面给出正确代码。。。
#include<cstdio>#include<iostream>#include<algorithm>#define N 1000001using namespace std;int n,a[N],tmp[N];long long ans;int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f;}void gsort(int l,int r){ if(l==r) return ; int mid=(l+r)/2; gsort(l,mid);gsort(mid+1,r); int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(a[i]<=a[j]) tmp[k++]=a[i++]; else { ans+=(long long)(mid-i+1); tmp[k++]=a[j++]; } } while(i<=mid) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int i=l;i<=r;i++) a[i]=tmp[i]; }int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); gsort(1,n); cout<<ans; return 0;}
hzwer与逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。