欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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组。