题解：P5870 [SEERC 2018] Modern Djinn

Lu_Yu_hao · 2025-03-01 09:45:29 · 题解

这道题还算难的。

原先我的时间复杂度为 O(T \times M^2)，要想不超时应降到 O(T \times M) 及以下。

方法是使用哈希表（unordered map）统计每个人 Y 被多少愿望指向，这样就可以在 O(M) 的时间内统计每个愿望的影响范围。

我们还要使用贪心，按照影响范围从大到小排序，选择前 ⌊M/4⌋ + 1 个愿望。

即使这样也会超时，我们要在排序上动手脚，使用快速排序找到前 K 个最大的影响范围，完全排序肯定超时。

时间复杂度 O(T \times M)，对于：

是完全可以过的。

代码重要部分：

  while (T--) {
        int N, M;
        cin >> N >> M;
        vector<pair<int, int>> wishs(M);
        for (int i = 0; i < M; ++i) {
            cin >> wishs[i].first >> wishs[i].second;
        }
        // 预处理每个人的愿望列表
        vector<vector<int>> wish(N + 1);
        for (int i = 0; i < M; ++i) {
            int X = wishs[i].first;
            wish[X].push_back(i);
        }

        // 统计每个愿望的影响范围
        vector<int> fanwei(M, 0);
        for (int i = 0; i < M; ++i) {
            int Y = wishs[i].second;
            fanwei[i] = wish[Y].size();
        }

        // 按照影响范围从大到小排序
        vector<int> paixv(M);
        for (int i = 0; i < M; ++i) {
            paixv[i] = i;
        }
        sort(paixv.begin(), paixv.end(), [&](int a, int b) {
            return fanwei[a] > fanwei[b];
        });
}

因为怕抄题解，所以给重要部分（其实也就省去了输入和输出）。

为了让大家理解，数组名特意改了。