C/C++课程中，log2000为春季学期2017年的算法实验（1-3）
发布时间
阅读量：
阅读量
分治策略解决逆序对问题
对于一个整数序列A=(A1,A2,…An)，当满足i<j且Ai>Aj时，<I,j>将构成一个逆序对。数组长度n的取值范围为1≤n≤30000。例如，在数组（3，1，4，5，2）中，存在的逆序对包括<3,1>、<3,2>、<4,2>以及<5,2>。
输入内容包含两个部分：整数n和数组A。
输出结果为逆序对的总数。
示例输入：
5
3 1 4 5 2
示例输出：
4
asw:
#include<stdio.h>
#define M 100
int main()
{
int i, j;
int size;
int data[M];
scanf("%d",&size);
int result=0; //计算出的逆序对数
for (j = 0; j<size; j++) scanf("%d",&data[j]);
for(i = 0; i < size; ++i)
{
for(j = i+1; j < size; ++j)
{
if(data[i] > data[j])
{
++result;全部评论 (0)
还没有任何评论哟~