归并
我想写个指针怎么就这么难
挂掉的指针代码
#include
using namespace std;
int n,a[100010];
int p1,p2;
void merge(int p1,int mid,int p2)
{
int n1=mid-p1+1,n2=p2-mid;
int *l=new int[n1],*r=new int[n2];
for(int i=0;i 过掉的数组代码
#include
#include
#include
#include
#include
#include
using namespace std;
int n,a[500010],ans[500010];
long long cnt;
void merge(int p1,int p2)
{
if(p1==p2)return;
int mid=(p1+p2)/2,i=p1,j=mid+1,k=p1;
merge(p1,mid);
merge(mid+1,p2);
while(i<=mid&&j<=p2)
{
if(a[i]<=a[j])ans[k++]=a[i++];
else
{
ans[k++]=a[j++];
cnt+=mid-i+1;
}
}
while(i<=mid)
ans[k++]=a[i++];
while(j<=p2)
ans[k++]=a[j++];
for(int l=p1;l<=p2;l++)
a[l]=ans[l];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
merge(1,n);
printf("%lld",cnt);
return 0;
}
//可能写指针不是个好兆头把（误
//另外：STL大法好啊
merge(first1,last1,first2,last2,result,compare);见瑞士轮
result为存放结果的容器，comapre为比较函数（可略写，默认为合并为一个升序序列）。