HDU 3743 Frosh Week(归并排序求逆序对)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 3743 Frosh Week(归并排序求逆序对)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1719字，纯文字阅读大概需要3分钟。
内容图文
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3743
题目意思就是给你一个长为n的序列,让你求逆序对.我用的是归并排序来求的.归并排序有一个合并的过程,分前后两段,当a[i] > a[j]时,说明a[j]比前面那段啊[i],a[i+1],a[i+2]....,a[mid],比这些都要小,所以总逆序对数要加上mid-i+1.
1
//
File Name: HDU3743.cpp
2
//
Author: xiaxiaosheng
3
//
Created Time: 2015年03月09日 星期一 21时54分45秒
4
5 #include<vector>
6 #include<list>
7 #include<map>
8 #include<set>
9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
2425usingnamespace std;
26typedef __int64 INT;
27constint maxn = 10e6+10;
2829int n,A[maxn],temp[maxn];
30INT ans;
31void merger(int *A,int s,int mid,int e)
32{
33int k = 0,i = s,j = mid+1;
34while(i <= mid && j <= e)
35 {
36if(A[i] < A[j])
37 temp[k++] = A[i++];
38else39 {
40 ans += (mid-i+1);
41 temp[k++] = A[j++];
42 }
43 }
44while(i <= mid) temp[k++] = A[i++];
45while(j <= e) temp[k++] = A[j++];
46for(int i = 0;i < k;++i)
47 A[s+i] = temp[i];
48}
49void mergersort(int *A,int s,int e)
50{
51if(s < e)
52 {
53int mid = (s + e) / 2;
54 mergersort(A,s,mid);
55 mergersort(A,mid+1,e);
56 merger(A,s,mid,e);
57 }
5859}
60int main(){
61while(scanf("%d",&n)!=EOF)
62 {
63for(int i = 0;i < n;++i)
64 scanf("%d",&A[i]);
65 ans = 0;
66 mergersort(A,0,n-1);
67 printf("%I64d\n",ans);
68 }
69return0;
70 }
原文：http://www.cnblogs.com/xiaxiaosheng/p/4324816.html
内容总结
以上是互联网集市为您收集整理的HDU 3743 Frosh Week(归并排序求逆序对)全部内容，希望文章能够帮你解决HDU 3743 Frosh Week(归并排序求逆序对)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。