51NOD 1019 逆序数
程序员文章站
2022-05-11 17:04:08
...
明知道明天就要考线代,死活不想复习,要是明天出考场的我回想起昨天晚上的自己还在写代码没复习,会不会想把自己剁了?
当然最简单直接的想法就是一个个数啦,很容易就能写出以下的代码:
#include <stdio.h>
int inversionOfArray(int a[],int n)//统计整体的逆序数
{
int i,sum=0;
for(i=0;i<n;i++)
sum+=inversionPerElement(a,i);
return sum;
}
int inversionPerElement(int a[],int index)//统计单个的逆序数
{
if(index==0) return 0;
else
{
int num=a[index],cnt=0;//从index-1向下遍历,cnt作为计数器
for(index--;index>=0;index--)
if(a[index]>num)
cnt++;
return cnt;
}
}
int main(int argc, char const *argv[])
{
int n,i,*p;
scanf("%d",&n);
p=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("%d",inversionOfArray(p,n));
free(p);
return 0;
}
冷静下来想一想,我们实际上做了两次遍历, 实际循环部分相当于
for(i=0;i<n;i++)
for(j=0;j<i;j++)
化成平面图就是一个三角形, 显然,这是一个O(n^2)的算法。
实际上也只能过前20组。
上一篇: 51Nod 1019树状数组离散化
下一篇: Kubernetes volumes简介