题解：CF2060B Farmer John's Card Game

_second_coming_ · 2025-01-22 21:12:06 · 题解

题解：CF2060B Farmer John's Card Game

解题思路

根据题目要求，每头奶牛的牌必须满足以下条件：\ 每头奶牛的牌对 n 取模的结果必须相同，即 a \bmod n = c。其中 a 是牌的编号，c 是固定的余数。 要按照每头奶牛的第一张牌从小到大排序，构造合法的出牌顺序。

关键点解释

排序依据：根据每头奶牛的第一张牌排序，因为第一张牌最小，决定了奶牛的顺序。\ 合法性检查：通过检查每头奶牛的牌对 n 取模的结果是否一致，确保所有奶牛的牌可以按照某种顺序出完。\ 输出结果：如果合法，输出排列 p；否则输出 -1。

代码

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

const int inf = 1e16, maxn = 2010;
int a[maxn][maxn], p[maxn];

bool cmp(int aa, int bb) {
    return a[aa][1] < a[bb][1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        // 读取每头奶牛的牌，并对每头奶牛的牌排序
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
            sort(a[i] + 1, a[i] + m + 1);  // 对每头奶牛的牌排序
        }

        // 初始化排列 p
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        // 按每头奶牛的第一张牌排序
        sort(p + 1, p + n + 1, cmp);

        // 检查是否满足条件：每头奶牛的牌对 n 取模的结果是否相同
        bool valid = true;
        for (int i = 1; i <= n && valid; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[p[i]][j] % n != (i - 1)) {
                    valid = false;
                    break;
                }
            }
        }

        // 输出结果
        if (!valid) {
            cout << "-1\n";
        } else {
            for (int i = 1; i <= n; i++) {
                cout << p[i] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}