每天一道 CodeForces 构造/思维题 （day2）

@TOC

1题目

题目链接 C.Column Swapping

题目大意：给你一个二维矩阵，问是否能够交换两列，使得每一行都是非递减的

2思路

条件：

1. 只能交换两列
2. 每一行非递减

我们可以枚举每一行，将每一行从到大排个序，然后与原来的行比对，如果在同一位置上元素不同，那么这一元素一定是要被交换的，我们记录下所有在需要交换的元素个数cnt

1. cnt == 0，表示没有元素被交换，继续找下一行
2. cnt == 2，表示有两个元素需要交换，记录下这两个位置l和r。以便后续处理
3. cnt > 2，表示有三个以上元素被交换了，那么不满足条件1

cnt==2时，我们已经知道需要某一行需要交换两个位置了，但不代表其他行交换这两位置之后也满足条件，我们需要将其他行的这两列交换后，看满不满足此行满足条件2，枚举每一行即可，如果最后都满足，那么就输出l和r。

3代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
void solve()
{
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            scanf("%d", &g[i][j]);
    }
    vector<int> v;
    int l = -1, r = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        v = g[i];
        sort(v.begin(), v.end());
        for (int j = 0; j < m; j++)
        {
            if (v[j] != g[i][j])
            {
                if (l == -1)
                    l = j;
                else
                    r = j;
                cnt++;
            }
        }
        if (cnt)
            break;
    }
    if (cnt > 2)
    {
        cout << "-1\n";
        return;
    }
    if (cnt == 0)
    {
        cout << "1 1\n";
        return;
    }
    for (int i = 0; i < n; i++)
    {
        v = g[i];
        int cnt = 0;
        swap(g[i][l], g[i][r]);
        for (int j = 1; j < m; j++)
        {
            if (g[i][j] < g[i][j - 1])
            {
                cout << "-1\n";
                return;
            }
        }
    }
    cout << l + 1 << " " << r + 1 << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}