首页 > 代码库 > UVa 299 - Train Swapping
UVa 299 - Train Swapping
题目:给你一个序列,每次只能交换相邻的两个数,问使得序列递增的最小的交换次数。
分析:数学,逆序数。
如果在一个序列中存在a[i] > a[j]并且 i < j,则a[i]与a[j]构成一对逆序对;
一个序列的逆序对的总数,就是这个序列的逆序数;
如题,相邻元素交换,每次交换序列逆序数必然改变1,而一个递增的序列逆序数为0;
因此,最少的交换次数即为逆序数,而每次按照逆序对减少的方式交换就得到递增序列。
说明:整理很久以前刷过的题目。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; int data[100]; int main() { int n,m,count; while (cin >> n) while (n --) { cin >> m; for (int i = 0 ; i < m ; ++ i) cin >> data[i]; count = 0; for (int i = 0 ; i < m ; ++ i) for (int j = 0 ; j < i ; ++ j) count += (data[j]>data[i]); cout << "Optimal train swapping takes " << count << " swaps." << endl; } return 0; }
UVa 299 - Train Swapping
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。