求助站外题
  • 板块学术版
  • 楼主xdcm
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/5 13:35
  • 上次更新2023/10/27 16:54:49
查看原帖
求助站外题
681223
xdcm楼主2022/8/5 13:35

有 n 个数 a1,a2,…,an,对于其中的两个数字x,y,如果满足 x 出现的位置在 y 出现的位置前面 并且 x 比 y 大,则称 (x,y) 为数组 a 的一个逆 序对。请问数组 a 的逆序对一共有多少个。形式的说,请求出有多少组 (i,j) 满足 i<j 并ai>aj。

输入格式

第一行一个整数n。

接下来一行n个整数,a1,a2,…,an。

输出格式

一个数,表示答案。

样例输入

4 4 2 3 1

样例输出

5

样例解释

5 个逆序对分别为 (4,2),(4,3),(4,1),(2,1),(3,1)。

数据范围

对于 100% 的数据,保证 2≤n≤100000,1≤ai≤n 并且每个数字都只会出现一次。

我的代码

#include <bits/stdc++.h>
using namespace std;
long long n,i,j,sum;
int main()
{
	cin>>n;
	long long a[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			if(a[j]>a[i] && j<i)
			{
				sum++;
			}
		}
	}
	cout<<sum;
}

为啥会的0分??

2022/8/5 13:35
加载中...