题解：P5870 [SEERC 2018] Modern Djinn

这道题还算难的。

原先我的时间复杂度为

O(T \times M^2)

，要想不超时应降到

O(T \times M)

及以下。

方法是使用哈希表（unordered map）统计每个人

Y

被多少愿望指向，这样就可以在

O(M)

的时间内统计每个愿望的影响范围。

我们还要使用贪心，按照影响范围从大到小排序，选择前

⌊M/4⌋ + 1

个愿望。

即使这样也会超时，我们要在排序上动手脚，使用快速排序找到前

K

个最大的影响范围，完全排序肯定超时。

时间复杂度

O(T \times M)

，对于：

T:10^4

M:10^5 \times 2

是完全可以过的。

代码重要部分：

CPP

  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];
        });
}

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

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

题解：P5870 [SEERC 2018] Modern Djinn

文章操作

相关推荐

评论

题解：P5870 [SEERC 2018] Modern Djinn