洛谷P1908 逆序对(归并排序)
2024-09-02 11:30:08
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入输出格式
输入格式:
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。
输出格式:
给定序列中逆序对的数目。
输入输出样例
说明
对于50%的数据,n≤2500
对于100%的数据,n≤40000。
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int MAXN=;
inline int read()
{
char c=getchar();int x=,flag=;
while(c<''||c>'') {if(c=='-') flag=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-,c=getchar();return x*flag;
}
int n;
int a[MAXN];
int tmp[MAXN];
int ans=;
void Sort(int l,int r)
{
if(l==r) return ;
int mid=l+r>>;
Sort(l,mid);Sort(mid+,r);
int nowl=l,nowr=mid+,nowpos=l;
while(nowl<=mid&&nowr<=r)
{
if(a[nowl]<=a[nowr]) tmp[nowpos++]=a[nowl],nowl++;
else tmp[nowpos++]=a[nowr],nowr++,ans=ans+mid-nowl+;
}
while(nowl<=mid) tmp[nowpos++]=a[nowl],nowl++;
while(nowr<=r) tmp[nowpos++]=a[nowr],nowr++;
for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main()
{
n=read();
for(int i=;i<=n;i++) a[i]=read();
Sort(,n);
printf("%d",ans);
return ;
}
最新文章
- Asp.net MVC+Bootstrap3的悬浮式登录框效果
- MemCache在win7上的可视化配置以及Nodejs/Net应用
- angular学习的一些小笔记(中)之双向数据绑定
- C#字符操作
- halcon学习之产品检测
- zoj 3229 Shoot the Bullet(无源汇上下界最大流)
- C语言课本实例
- [Java,JavaEE] 最常用的Java库一览
- 给TextView中的text上下左右添加一张图片
- Css样式之overflow
- PuTTY 信息泄露漏洞
- Hacker(22)----解除系统中的密码
- 开启真机的View Server引入HierarchyViewer/By写monkeyrunner自动化测试脚本
- luogu1001 A+B Problem
- Springboot - 学习笔记 ②
- Hadoop2.4.1伪分布式安装
- linux:CPU私有变量(per-CPU变量)
- 深度学习+CRF解决NER问题
- 『计算机视觉』Mask-RCNN_从服装关键点检测看KeyPoints分支
- python中匿名函数lambda