小红的示例检索重排

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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

    int N;
    cin >> N;
    vector<double> rel(N);
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) {
        cin >> rel[i] >> ids[i];
    }

    vector<vector<double>> sim(N, vector<double>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> sim[i][j];
        }
    }

    double lambda;
    int K;
    cin >> lambda >> K;

    if (K == 0) {
        cout << endl;
        return 0;
    }

    vector<bool> selected(N, false);
    vector<double> best_sim(N, 0.0);   // 每个文档与当前已选集合的最大相似度
    vector<int> ans;

    const double eps = 1e-9;

    for (int t = 0; t < K; ++t) {
        double best_mmr = -1e9;
        int best_idx = -1;

        for (int i = 0; i < N; ++i) {
            if (selected[i]) continue;
            double mmr = lambda * rel[i] - (1.0 - lambda) * best_sim[i];
            if (best_idx == -1 || mmr > best_mmr + eps) {
                best_mmr = mmr;
                best_idx = i;
            } else if (fabs(mmr - best_mmr) < eps && ids[i] < ids[best_idx]) {
                best_idx = i;
            }
        }

        // 理论上必能找到
        selected[best_idx] = true;
        ans.push_back(ids[best_idx]);

        // 更新 best_sim
        for (int j = 0; j < N; ++j) {
            if (!selected[j]) {
                best_sim[j] = max(best_sim[j], sim[j][best_idx]);
            }
        }
    }

    for (size_t i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }
    cout << endl;

    return 0;
}