洛谷 B4361：[GESP202506 四级] 排序

【题目来源】https://www.luogu.com.cn/problem/B4361【题目描述】体育课上有 n 名同学排成一队从前往后数第 i 位同学的身高为 hi体重为 wi​。目前排成的队伍看起来参差不齐老师希望同学们能按照身高从高到低的顺序排队如果身高相同则按照体重从重到轻排序。在调整队伍时每次只能交换相邻两位同学的位置。老师想知道最少需要多少次交换操作才能将队伍调整成目标顺序。【输入格式】第一行一个正整数 n表示队伍人数。接下来 n 行每行两个正整数 hi 和 wi分别表示第 i 位同学的身高和体重。【输出格式】输出一行一个整数表示最少需要的交换次数。​​​​​​​【输入样例】51 603 702 804 554 50【输出样例】8【数据范围】对于所有测试点保证 1≤n≤30000≤hi,wi≤10^9。【算法分析】这题本质上是一个求逆序对数量的问题。题目要求将队伍按身高从高到低排序身高相同时按体重从重到轻排序每次只能交换相邻两位同学。最少交换次数等于当前排列与目标排列之间的逆序对数量。【算法代码】#include bits/stdc.h using namespace std; const int N3e35; int h[N],w[N]; int n; int main() { cinn; for(int i1; in; i) { cinh[i]w[i]; } int ans0; for(int i1; in; i) { for(int ji1; jn; j) { if(h[i]h[j] || (h[i]h[j] w[i]w[j])) { ans; } } } coutansendl; return 0; } /* in: 5 1 60 3 70 2 80 4 55 4 50 out: 8 */【参考文献】https://gesp.ccf.org.cn/101/attach/1687195991670816.pdfhttps://www.luogu.com.cn/problem/solution/B4361