当前位置:首页 > 题解目录 > 正文内容

【题解】光荣的梦想

亿万年的星光4年前 (2022-04-09)题解目录1709

【题目描述】

Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量,平衡瞬间即被打破。KB决定求助于你,帮助他完成这个梦想。

一串数列即表示一个世界的状态。

平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

【输入描述】

第一行为数列中数的个数n,第二行为n ≤ 10000个数。表示当前数列的状态。

【输出描述】

输出一个整数,表示最少需要交换几次能达到平衡状态。

【样例输入】

4
2 1 4 3

【样例输出】

2

【题目分析】

  • 注:此题还有另外一种描述:给定一个序列 a1,a2,…,an,如果存在 i<j 并且 ai>aj ,那么我们称之为逆序对,求逆序对的数目。

  • 归并排序和分治法的应用



【参考代码—递归解法】

#include <bits/stdc++.h> 
using namespace std;
 
int ans=0, tmp=0;
int a[10005];
void recursive(int);
 
int main()
{
    int n;
    scanf ("%d", &n);
	for (int i=0; i<n; i++) {
		scanf ("%d", &a[i]);
	} 
	for (int i=0; i<n; i++)
		recursive(n);
	printf ("%d", ans);
    return 0;
}
 
void recursive(int n) {
	if (n == 1) {
		return ;
	}
	if (a[n-1] < a[n-2]) {
		ans++;
		tmp = a[n-1];
		a[n-1] = a[n-2];
		a[n-2] = tmp;
	}
	recursive(n-1);
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

分数求和

题目描述】输入n个分数并对他们求和,并用最简形式表示。所谓最简形式是指:分子分母的最大公约数为1;若最终结果的分母为1,则直接用整数表示。如: 5/6  、 10/3  均是最简形...

【题解】最大配对

题目描述      给出2个序列A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]},从A、B中各选出n个元素进行一一配对(可以不按照原来在...

【题解】小X与机器人

【题解】小X与机器人

【题目描述】小X的老师很喜欢围棋。众所周知,围棋的棋盘有19行19列,共有361个交叉点。为方便起见,我们把这些行列按顺序编号为1~19,并用(x, y)表示第x列第y行的位置。例如下图中,A用(16...

简单算术表达式求值

【题目描述】 两位正整数的简单算术运算(只考虑整数运算),算术运算为:+,加法运算;    -,减法运算;   &nbs...

【题解】黑白棋子移动

【题目描述】有2n个棋子(n≥4)排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形:○○○○○●●●●●移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可...

【题解】马拦过河卒

【题解】马拦过河卒

【题目描述】棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。...