题解 P1086 【花生采摘】

2019 年 08 月 13 日

1206 次浏览

936字数

咱可能是第一个用 **优先队列** 做这道题的人
首先看到这道题说要从大到小的摘花生，
一个接一个，这个挖完要挖下一个怎么办？
所以可以想到用队列，吃一个pop一个
怎么完成从大到小的排序呢？
优先队列直接帮你排好！
剩下的就是一些简单的模拟，**/具体内容在代码中的注释/**

```cpp
#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

struct hs //指花生:)
{
    int x, y, v;
    bool operator < (const hs & a) const
    {
        return v < a.v;
    }//优先队列默认从大到小排序，但是需要用到小于号，所以这里重载运算符 < (只重载<就可以了)
};

priority_queue <hs> q;

int main()
{
    int m, n, k;
    int sum = 0;
    cin >> m >> n >> k;
    int a;
    hs t;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
        {
            cin >> a;
            t.v = a;
            t.x = j;
            t.y = i;
            if(a != 0) //如果有数值，就推进队列
                q.push(t);
        }
    k -= q.top().y; //走到最大的花生植株
    while(!q.empty() && k > q.top().y) //第一个是检验队列不为空，如果空了说明全摘完了，第二个是检验剩余的时间可以走回路边
    {
        k--; //只要进入一次循环，说明到了一棵植株，采摘耗费1时间
        sum += q.top().v;
        int lx = q.top().x, ly = q.top().y;
        q.pop();//换下一棵树
        k -= abs(lx - q.top().x) + abs(ly - q.top().y);//剩余的时间减去从上一棵植株到这棵的时间
    }
    cout << sum << endl;
    return 0;
}
```