洛谷 P1908
程序员文章站
2022-04-09 19:42:14
[TOC] 题目 "戳" 思路:归并排序求逆序对 $Code$ cpp include include include include include using namespace std; int n,a[500001],temp[500001]; long long ans; inline i ......
目录
题目
思路:归并排序求逆序对
$code$
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; int n,a[500001],temp[500001]; long long ans; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } inline void merge_sort(int l,int r,int mid){ int i=l,j=mid+1,tot=0; while(i<=mid&&j<=r){ if(a[i]>a[j]){ ans+=mid-i+1;//当a[i]这个点大于a[j]时a[i~mid]都大于a[j](因为是排好序的)。 temp[++tot]=a[j++]; }else temp[++tot]=a[i++]; } while(i<=mid){ temp[++tot]=a[i++]; } while(j<=r){ temp[++tot]=a[j++]; } for(int k=1;k<=tot;++k){ a[l++]=temp[k]; } } void merge(int l,int r){ if(l==r) return; int mid=(l+r)>>1; merge(l,mid);merge(mid+1,r); merge_sort(l,r,mid); } int main(){ n=read(); for(int i=1;i<=n;++i){ a[i]=read(); } merge(1,n); printf("%lld",ans); return 0; }
双倍经验
上一篇: SQL子连接案例