优先队列的为什么过不了QAQ

P1434 [SHOI2002] 滑雪

IsQian @ 2023-11-07 17:29:55

参考了解答区的一位使用优先队列的,为什么我的总是过不了?QAQ

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 200;
int Height[N][N], maxHigh[N][N];
struct Item {
    int val;
    pair<int, int> indices;
    Item(int v, int i, int j) : val(v), indices(make_pair(i, j)) {}
};
struct Compare {
    bool operator()(const Item &a, const Item &b) {
        return a.val > b.val;
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    memset(maxHigh, 0, sizeof(maxHigh));
    memset(Height, 0, sizeof(Height));
    priority_queue<Item, vector<Item>, Compare> pq;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> Height[i][j];
            pq.push(Item(Height[i][j], i, j));
        }
    }
    int res = 1;
    while (!pq.empty()) {
        Item item = pq.top();
        int val = item.val, i = item.indices.first, j = item.indices.second;
        if (val > Height[i - 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i - 1][j] + 1);
        if (val > Height[i][j + 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j + 1] + 1);
        if (val > Height[i + 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i + 1][j] + 1);
        if (val > Height[i][j - 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j - 1] + 1);
        res = max(res, maxHigh[i][j]);
        pq.pop();
        //cout << res << "(" << i << "," << j << ") " << val << endl;
    }
    cout << res << "\n";
    return;
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

by KinoTsuki @ 2024-01-03 22:32:28

@heiheiwolala

应该由海拔从低到高枚举

struct Compare {
    bool operator()(const Item &a, const Item &b) {
        return a.val < b.val;
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    memset(maxHigh, 0, sizeof(maxHigh));
    memset(Height, 0, sizeof(Height));
    priority_queue<Item, vector<Item>, Compare> pq;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> Height[i][j];
            pq.push(Item(Height[i][j], i, j));
        }
    }
    int res = 0;
    while (!pq.empty()) {
        Item item = pq.top();
        int val = item.val, i = item.indices.first, j = item.indices.second;
        if (val < Height[i - 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i - 1][j] + 1);
        if (val < Height[i][j + 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j + 1] + 1);
        if (val < Height[i + 1][j]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i + 1][j] + 1);
        if (val < Height[i][j - 1]) maxHigh[i][j] = max(maxHigh[i][j], maxHigh[i][j - 1] + 1);
        res = max(res, maxHigh[i][j]);
        pq.pop();
        //cout << res << "(" << i << "," << j << ") " << val << endl;
    }
    cout << res+1 << "\n";
    return;
}

这样就能过了 OAO


|