首页 > 代码库 > 逆序对
逆序对
1688 求逆序对
测试通过 Accepted
总耗时: 525 ms
0 / 0 数据通过测试.
最近的错误点信息
运行结果
测试点#deseq0.in 结果: 内存使用量: 1772kB 时间使用量: 84ms 测试点#deseq1.in 结果: 内存使用量: 128kB 时间使用量: 1ms 测试点#deseq2.in 结果: 内存使用量: 256kB 时间使用量: 1ms 测试点#deseq3.in 结果: 内存使用量: 360kB 时间使用量: 10ms 测试点#deseq4.in 结果: 内存使用量: 1768kB 时间使用量: 64ms 测试点#deseq5.in 结果: 内存使用量: 1768kB 时间使用量: 63ms 测试点#deseq6.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq7.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq8.in 结果: 内存使用量: 1772kB 时间使用量: 82ms 测试点#deseq9.in 结果: 内存使用量: 1768kB 时间使用量: 80ms
错误error
测试点#deseq0.in 结果: 内存使用量: 1772kB 时间使用量: 84ms 测试点#deseq1.in 结果: 内存使用量: 128kB 时间使用量: 1ms 测试点#deseq2.in 结果: 内存使用量: 256kB 时间使用量: 1ms 测试点#deseq3.in 结果: 内存使用量: 360kB 时间使用量: 10ms 测试点#deseq4.in 结果: 内存使用量: 1768kB 时间使用量: 64ms 测试点#deseq5.in 结果: 内存使用量: 1768kB 时间使用量: 63ms 测试点#deseq6.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq7.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq8.in 结果: 内存使用量: 1772kB 时间使用量: 82ms 测试点#deseq9.in 结果: 内存使用量: 1768kB 时间使用量: 80ms
错误信息
测试点#deseq0.in 结果: 内存使用量: 1772kB 时间使用量: 84ms 测试点#deseq1.in 结果: 内存使用量: 128kB 时间使用量: 1ms 测试点#deseq2.in 结果: 内存使用量: 256kB 时间使用量: 1ms 测试点#deseq3.in 结果: 内存使用量: 360kB 时间使用量: 10ms 测试点#deseq4.in 结果: 内存使用量: 1768kB 时间使用量: 64ms 测试点#deseq5.in 结果: 内存使用量: 1768kB 时间使用量: 63ms 测试点#deseq6.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq7.in 结果: 内存使用量: 1768kB 时间使用量: 70ms 测试点#deseq8.in 结果: 内存使用量: 1772kB 时间使用量: 82ms 测试点#deseq9.in 结果: 内存使用量: 1768kB 时间使用量: 80ms
题目描述 Description
给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目
数据范围:N<=105。Ai<=105。时间限制为1s。
输入描述 Input Description
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
1 #include<iostream>//逆序对 2 #include<cstring> 3 using namespace std; 4 long long int a[1000001]; 5 long long int tot; 6 long long int n; 7 long long int ans[1000001]; 8 long long int now; 9 void f(long long int s,long long int t) 10 { 11 if(s==t)return; 12 int mid=(s+t)/2; 13 f(s,mid); 14 f(mid+1,t);//递归调用 15 long long int i=s; 16 long long int j=mid+1; 17 now=s; 18 while(i<=mid&&j<=t) 19 { 20 if(a[i]<=a[j])//前半段小于后半段 21 ans[now++]=a[i++];//ans数组用于存储当前答案 22 else 23 { 24 tot+=mid-i+1;//后半段大,将前段剩余部分加入答案 25 ans[now++]=a[j++];//将后半段存入 26 } 27 } 28 while(i<=mid)//此while&&下while将多出的部分存入ans 29 ans[now++]=a[i++]; 30 while(j<=t) 31 ans[now++]=a[j++]; 32 for (i=s;i<=t;i++)//将ans存入a 33 a[i] = ans[i]; 34 } 35 int main() 36 { 37 long long int n; 38 cin>>n; 39 for(int i=1;i<=n;i++) 40 cin>>a[i]; 41 f(1,n); 42 cout<<tot; 43 return 0; 44 }
逆序对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。