✏️ 纠错
第 131 题 / 共 155 题
题目描述
体育课上有 n 名同学排成一队,从前往后数第 i 位同学的身高为 hi,体重为 wi。目前排成的队伍看起来参差不齐,老师希望同学们能按照身高从高到低的顺序排队,如果身高相同则按照体重从重到轻排序。在调整队伍时,每次只能交换相邻两位同学的位置。老师想知道,最少需要多少次交换操作,才能将队伍调整成目标顺序。
输入格式
第一行,一个正整数 n,表示队伍人数。
接下来 n 行,每行两个正整数 hi 和 wi,分别表示第 i 位同学的身高和体重。
输出格式
输出一行,一个整数,表示最少需要的交换次数。
输入输出样例
输入 #1
5 1 60 3 70 2 80 4 55 4 50
输出 #1
8
输入 #2
5 4 0 4 0 2 0 3 0 1 0
输出 #2
1
说明/提示
对于所有测试点,保证 1≤n≤3000,0≤hi,wi≤109。
你真棒!
📝 题目解析
【解题思路】
这道题要求将同学按身高从高到低、身高相同时按体重从重到轻排序,并计算最少的相邻交换次数。关键在于理解交换次数与逆序对数量的关系。
首先,使用scanf读取队伍的人数n。
然后,使用vector<pair<int, int>> 存储每个同学的身高和体重。
接着,使用两层嵌套循环遍历所有同学对,如果a[i] < a[j],说明需要交换这两个同学的位置,将交换次数ans加1。
最后,输出交换次数ans。
参考程序
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n, ans = 0;
scanf("%d", &n);
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++)
scanf("%d%d", &a[i].first, &a[i].second);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] < a[j])
ans++;
cout << ans << '\n';
return 0;
}