题解 - P10451 Innovative Business

· · 题解

思路

本题说：

关系具有反对称性，但不具有传递性。

这个性质满足归并排序的性质。

所以可以在归并排序的时候询问两两的大小关系，只需要加一个比较函数即可：

bool compare(int a, int b) {
    cout << "? " << a << ' ' << b << endl;
    bool t;
    cin >> t;
    return t;
}

代码

话不多说，直接上代码：

#include <iostream>
using namespace std;

const int N = 1e3 + 5;

int n;
int a[N];
int t[N];

bool compare(int a, int b) {
    cout << "? " << a << ' ' << b << endl;
    bool t;
    cin >> t;
    return t;
}

void Merge_sort(int le, int rt) {
    if (le == rt)
        return;

    int mid = (le + rt) / 2;
    Merge_sort(le, mid);
    Merge_sort(mid + 1, rt);
    int i = le, j = mid + 1, k = le;

    while (i <= mid && j <= rt) {
        if (compare(a[i], a[j])) {
            t[k] = a[i];
            i ++ ;
        } else {
            t[k] = a[j];
            j ++ ;
        }

        k ++ ;
    }

    while (i <= mid) {
        t[k] = a[i];
        i ++ ;
        k ++ ;
    }

    while (j <= rt) {
        t[k] = a[j];
        j ++ ;
        k ++ ;
    }

    for (int x = le; x <= rt; x ++ )
        a[x] = t[x];
}

void inp() {
    cin >> n;
}

void work() {
    for (int i = 1; i <= n; i ++ )
        a[i] = i;

    Merge_sort(1, n);
    cout << "!";

    for (int i = 1; i <= n; i ++ )
        cout << " " << a[i];

    puts("");
}

int main() {
    inp();
    work();

    return 0;
}

完结撒花！