C++题目描述给定一个数列a这个数列满足ai≠aji≠j现在要求你把这个数列从小到大排序每次允许你交换其中任意一对数请问最少需要几次交换？输入描述第一行是一个整数代表数字个数n。第二行有n个整数用空格分隔开表示数列a。输出描述只有一行包含一个数表示最少的交换次数。样例1输入88 23 4 16 77 -5 53 100输出5提示数据规模与约定对于100的数据保证1≤n≤1e5−2^31ai2^

思路:

由于数列中的数不能相等，所以将数列排序后，每个位置上的数应该是从小到大依次递增的。

我们可以遍历数列，记录当前位置上的数与它应该在的位置的数的差值的绝对值的和，即为最少交换次数。

具体实现:

1. 读入整数n，表示数字个数。
2. 读入n个整数，存入vector中。
3. 创建一个长度为n的vector，用于存储数列排序后的结果。
4. 遍历数列，计算每个位置上的数与它应该在的位置的数的差值的绝对值的和。
5. 输出最少交换次数。

代码实现如下:

#include #include #include using namespace std;

int main() { int n; cin >> n;

vector<int> nums(n);
for (int i = 0; i < n; i++) {
    cin >> nums[i];
}

vector<int> sortedNums(nums);
sort(sortedNums.begin(), sortedNums.end());

int minSwaps = 0;
for (int i = 0; i < n; i++) {
    if (nums[i] != sortedNums[i]) {
        minSwaps++;
    }
}

cout << minSwaps << endl;

return 0;