逆序对&求逆序对
2024-08-26 20:16:11
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入输出格式
输入格式:
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。
输出格式:
给定序列中逆序对的数目。
输入输出样例
输入样例#1:
6
5 4 2 6 3 1
输出样例#1:
11
说明
对于50%的数据,n≤2500
对于100%的数据,n≤40000。
思路:归并排序思想
代码实现:
#include<cstdio>
int n;
int s[],v[];
int gb(int x,int y){
if(x==y) return ;
int mid=(x+y)>>;
int ans=gb(x,mid)+gb(mid+,y);
int p=x,j=x,k=mid+;
while(j<=mid&&k<=y){
if(s[j]>s[k])
{ans+=mid-j+;v[p++]=s[k++];}
else v[p++]=s[j++];
}
while(j<=mid) v[p++]=s[j++];
while(k<=y) v[p++]=s[k++];
for(int i=x;i<=y;i++) s[i]=v[i];
return ans;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&s[i]);
printf("%d\n",gb(,n));
return ;
}
题目描述 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
略有改动即可。
代码实现:
#include<cstdio>
#include<iostream>
using namespace std;
long long ans,n;
int s[],v[];
void gbpx(int x,int y){
if(x==y) return;
int mid=(x+y)/;
gbpx(x,mid);gbpx(mid+,y);
int p=x,j=x,k=mid+;
while(j<=mid&&k<=y){
if(s[j]>s[k])
{ans+=mid-j+;v[p++]=s[k++];}
else v[p++]=s[j++];
}
while(j<=mid) v[p++]=s[j++];
while(k<=y) v[p++]=s[k++];
for(int i=x;i<=y;i++) s[i]=v[i];
}
int main(){
cin>>n;
for(int i=;i<=n;i++) cin>>s[i];
gbpx(,n);
cout<<ans<<endl;
return ;
}
题目来源:洛谷,CODE[VS]
最新文章
- 自定义iOS7导航栏背景,标题和返回按钮文字颜色
- 让C++程序打印自身源码
- Linux 下根据进程名kill进程
- UITableView动态存放、重用机制
- mysql没有delete操作,那是delete from操作,
- Linux 上的常用文件传输方式介绍与比较
- 1100. Mars Numbers (20)
- 优秀android开源项目与解决方案推荐
- sublime 配置
- 解决Twitter Bootstrap Tab URL链接问题
- 初级程序员应该了解的Linux命令
- Yaroslav and Sequence
- git pull 代码很慢的问题
- 第一种:NStread
- 成功解决react+webpack打包文件过大的问题
- C#WinCE程序(.NET Compact Framework 3.5)项目重构面向抽象设计
- python中的多线程和多进程编程
- 什么是L2 frame?
- BZOJ 1430 小猴打架 - prufer数列
- 总结的一些json格式和对象/String/Map/List等的互转工具类
热门文章
- (博弈论)51NOD 1069 Nim游戏
- srand()
- 402 Remove K Digits 移掉K位数字
- 260 Single Number III 数组中除了两个数外,其他的数都出现了两次,找出这两个只出现一次的数
- SqlServer数据库(可疑)解决办法
- 转】 Kafka文件存储机制那些事
- [转]ASP.NET MVC HtmlHelper扩展之Calendar日期时间选择
- Winform学习知识汇总
- CF822C Hacker, pack your bags!
- Android RxJava1.X升级到RxJava2.X笔记