p1098 逆序对
题目
输入格式:
第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。
输出格式:
给定序列中逆序对的数目。
数据范围:
对于50%的数据,n≤2500
对于100%的数据,n≤40000。
分析
使用分治的思想将序列不断分为两段,然后将这两段进行归并排序,因为每段已经排好序,所有每次增加的逆序对个数即为第一个(有序序列长度-需合并的位置+1)
同时我们还可以用树状数组求解,我们按大小排序,依次插入到它原本所在位置,所以逆序对个数即为在它之前插入的位置比它靠后的数的总个数
代码
归并排序版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int a[100000],t[100000];
int ans;
void mer(int le,int mid,int ri){
int i=le,j=mid+1,k=le;
while(i<=mid&&j<=ri){
if(a[i]>a[j]){
t[k++]=a[j++];
ans+=(mid-i+1);
}else t[k++]=a[i++];
}
for(i;i<=mid;i++)t[k++]=a[i];
for(j;j<=ri;j++)t[k++]=a[j];
for(i=le;i<=ri;i++)a[i]=t[i];
}
void go(int le,int ri){
if(le<ri){
int mid=(le+ri)>>1;
go(le,mid);
go(mid+1,ri);
mer(le,mid,ri);
}
}
int main(){
int n,m,i,j,k;
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
}
go(1,n);
cout<<ans<<endl;
return 0;
}
树状数组版
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
struct node {
int pl,d;
}a[110000];
int c[110000],n;
inline bool cmp(const node &x,const node &y){return x.d<y.d;}
inline int lb(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)c[x]+=k,x+=lb(x);}
inline int q(int x){int ans=0;while(x)ans+=c[x],x-=lb(x);return ans;}
int main()
{ int i,ans=0;
read(n);
for(i=1;i<=n;i++){
read(a[i].d);
a[i].pl=i;
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++){
add(a[i].pl,1);
ans+=i-q(a[i].pl-1)-1;
}
printf("%d\n",ans);
return 0;
}
最新文章
- (译)关于async与await的FAQ
- centos7 docker mysql56
- windows 10环境下 使用 msys2 + vs code 配置 c++ 的编译环境
- BZOJ2186 欧拉函数
- 出现错误ActivityManager: Warning: Activity not started, its current task has been
- A simple way for hover pop bootstrap nav-menu
- 有关opacity或RGBA设置颜色值及元素的透明值
- VS工程中添加c/c++工程中外部头文件及库的基本步骤
- python 自学之路-Day Two
- tp5.1中的容器和facade的实现
- 20180824fpreadforasp.net单元格类型绑定细则
- JS 私有变量
- C# 多线程參数传递
- 巧用Openlayers4的Style
- 第一章 :zabbix监控
- [转]VS 2012环境下使用MFC进行OpenGL编程
- react 带参数事件方法不立即执行
- notification的创建及应用
- RAID基本知识
- Scurm 术语