[COCI2009-2010#2] POSLOZI

Question

题目描述
给一个长度为
N
N 的排列 。有
M
M 种允许的修改方式 ，保证修改方式不重复，每种方式用
L
,
L,
R
R 来表示，意为你可以将下标为
L
L 的数与下标为
R
R 的数交换。

你可以修改该排列若干次，请给出一种修改方案，使原排列变为
1
,
1,
2
,
2,
3
,
3,
…
,
…,
N
N。如果有多种方案，输出修改次数最少的方案。如果还有多种方案，输出任意一组即可。

输入格式
第一行两个整数
N
,
N,
M
M。

第二行
N
N 个整数，表示排列。

接下来
M
M 行，第
i
i 行有两个整数，表示第
i
i 种修改方式。

输出格式
首行一个整数
o
p
e
_
c
n
t
ope_cnt，表示最少的修改次数。

接下来
o
p
e
_
c
n
t
ope_cnt 行，每行一个整数，表示进行第
i
i 种修改。

Sample Input 1
2 1
2 1
1 2
Sample Output 1
1
1
Sample Input 2
3 2
2 1 3
1 3
2 3
Sample Output 2
3
2
1
2
Sample Input 3
5 5
1 2 3 4 5
1 5
2 5
1 4
1 1
3 5
Sample Output 3
0
数据范围与约定
1
≤
N
≤
12
1≤N≤12

1
≤
M
≤
N
×
(
N
−
1
)
2
1≤M≤
2
N×(N−1)
​

COCI 2009.11.21 Round2 第五题

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    vector<pair<int, int>> operations(M);
    for (int i = 0; i < M; ++i) {
        cin >> operations[i].first >> operations[i].second;
    }

    // 计算每个位置的逆序对数量
    vector<int> inversions(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (arr[i] > arr[j]) {
                inversions[i]++;
            }
        }
    }

    // 寻找最少修改次数的方案
    int min_ops = N * (N - 1) / 2; // 最多需要交换的次数
    vector<int> best_operations;
    for (const auto& op : operations) {
        int l = op.first - 1;
        int r = op.second - 1;
        if (l > r) swap(l, r);

        // 尝试交换并更新逆序对数量
        if (arr[l] > arr[r]) {
            inversions[l]--;
            inversions[r]++;
        } else {
            inversions[l]++;
            inversions[r]--;
        }

        // 检查是否达到目标状态
        int current_ops = 0;
        for (int i = 0; i < N; ++i) {
            if (inversions[i] != 0) {
                current_ops += inversions[i];
            }
        }

        if (current_ops < min_ops) {
            min_ops = current_ops;
            best_operations.clear();
            best_operations.push_back(op.first);
        } else if (current_ops == min_ops) {
            best_operations.push_back(op.first);
        }
    }

    cout << min_ops << endl;
    for (int op : best_operations) {
        cout << op << endl;
    }

    return 0;
}