题目描述
给你一个序列x1,x2,…,xn,如果数对< xi,xj >,其中i< j,而xi> xj我们称之为逆序数对。 一个序列的逆序数对的数目,称为这个序列的逆序数。 比如说序列 3 1 2 ,逆序数对为 <3,1>和<3,2>,所以这个序列的逆序数为2。 现在给你一个数字序列,请求其逆序数。
输入
每个样例为两行,第一行为一个整数n(n≤1,000),表示序列中数字的个数,如果n为0,则表示输入结束,不需要处理。 第二行是n个整数xi,0≤xi≤100,000。输入数据保证序列中没有相同整数。
输出
每行输出一个整数,表示其序列数。
样例输入
3 3 1 2 4 1 2 3 4 0
样例输出
2 0
AC代码如下
#include<stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n!=0)
{
int num=0;
int a[100001];
int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
num++;
}
}
}
printf("%d\n",num);
}
return 0;
}
标签:xtu,xi,oj,int,样例,冒泡排序,num,序列,序数
From: https://blog.csdn.net/literature_art/article/details/143335704