题解 P1086 【花生采摘】
_Arahc_
·
·
题解
翻了这道题的前两页题解，没有几个和我的思路相仿的。唯一的一个我看不懂
首先为了让大家快速找到自己可能有的错误，把这道题的部分坑点给出来：
- 关于算法，题目已经明确规定了走法是按照花生数目由大到小摘花生：
鲁宾逊先生说：“你\color{red}\text{先找出花生最多}的植株，去采摘它的花生；然后\color{red}\text{再找出剩下的植株里花生最多的}，去采摘它的花生；\color{Blue}\text{依此类推}，不过你一定要在我限定的时间内回到路边。”
-
关于摘花生，将花生采摘下来是要耗费时间的。有同学没有+1，就会爆炸。
-
关于抄近道，题目虽然没有说清楚，但是不能通过在大路上抄近道省时间。
比如这样的情况，不能走红线，只能老老实实走蓝色路（曼哈顿）
- 关于第四个数据点：
1 1 5
15
如果你的答案是 45，请检查一下你是否重复在摘这个仅有的格子。
-
关于数组大小：开25*25绝对不会错。
-
对于没读好题目：保证没有花生数一样的格子，各位不要想太多。
-
考虑最终答案是0的情况，不要一上来就摘了花生回不去。
-
无脑抄袭我的代码或其他有反作弊措施的代码的人会体验CE的快感。
然后是我对这道题的分析：
做法比较明显，就是一步一步摘，判断会不会超时，然后算一个曼哈顿距离。
（曼哈顿距离公式：|x_{1}-x_{2}|+|y_{1}-y_{2}|）
各位的算法基本都是使用一个结构体，存储格子的坐标和花生数，有的人还存了时间，然后 sort 结构体，依次考虑摘不摘。
我的方法主要区别是省去了结构体和排序这两步。
我使用了一个 map（套 pair） 来存储一个格子的花生数目和坐标，这样当我选定一个花生数目的时候可以 O(1) 查询坐标。
对于从大到小排序，C++ 的STL的 \color{RoyalBlue}\text{priority queue} 可以 O(logn) 插入一个数。
使用 STL 就可以做到输入完成的时候就已经做好了花生数和坐标的绑定，以及一个排序。
这个算法坑在代码实现，最难的地方就是怎么拼写 \color{RoyalBlue}\text{priority queue}
解决方法也很简单，搜一下就可以了
\color{LimeGreen}\text{输入代码}
int n,m,k,a[23][23];
map<int,pair<int,int> >c;
priority_queue<int> q;
n=read(),m=read(),k=read();
for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j){
a[i][j]=read();
c[a[i][j]]=make_pair(i,j);
q.push(a[i][j]);
}
对于怎么处理：
每次取出大根堆的堆顶，依靠 map 锁定它的坐标，判断一下可不可以去摘就行。
为了防止\color{Red}\text{WA}声一片，使用 while(1)循环的童鞋最好提前处理第一株花生。
int j=q.top();q.pop();
int x=c[j].first;
int y=c[j].second;
int w=x+1;
每次+1的原因已经写在开头的第二点了。
现在每次处理就简单多了，如果可以摘（摘完了还能回家）就摘，然后再弹出下一个花生，锁定坐标（和距离），计算时间。
```cpp
while(w+x<=k){
s+=j;
if(q.empty()) break;
j=q.top();q.pop();
w+=abs(c[j].first-x)+abs(c[j].second-y)+1;
x=c[j].first,y=c[j].second;
}
```
注意要判断队列是否为空，否则会$\color{Orange}\text{90}$分，$\color{Red}\text{WA}$第4个数据，原因是这篇文章开头写的第四点。
最终是各位期待的完整代码（相信很多人直接跳过，空降到这里来了吧……）
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[23][23],w,s;
map<int,pair<int,int> >c; //绑定数量和坐标
priority_queue<int> q; //存花生数量的大根堆
int main(){
n=read(),m=read(),k=read();
for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j){
a[i][j]=read();
c[a[i][j]]=make_pair(i,j);// 绑定
q.push(a[i][j]); // 入队（堆）
}
//↑输入和预处理，现在所有花生大小坐标已绑定且排好序
int j=q.top();q.pop();//别像我一样把 top 写成 front
int x=c[j].first;
int y=c[j].second;// pair 不会的或 map 不会的可以自行百度
w+=x+1;
// ↑处理一下0的情况，即一个花生都摘不了
while(w+x<=k){
s+=j;
if(q.empty()) break;//这里不写就是90分
j=q.top();q.pop();
w+=abs(c[j].first-x)+abs(c[j].second-y)+1;//注意这里也要+1，别忘了
x=c[j].first,y=c[j].second;//更新位置
}
write(s);
return 0;
}
```
纯净无注释版本：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[23][23],w,s;
map<int,pair<int,int> >c;
priority_queue<int> q;
int main(){
n=read(),m=read(),k=read();
for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j){
a[i][j]=read();
c[a[i][j]]=make_pair(i,j);
q.push(a[i][j]);
}
int j=q.top();q.pop();
int x=c[j].first;
int y=c[j].second;
w+=x+1;
while(w+x<=k){
s+=j;
if(q.empty()) break;
j=q.top();q.pop();
w+=abs(c[j].first-x)+abs(c[j].second-y)+1;
x=c[j].first,y=c[j].second;
}
write(s);
return 0;
}
```
结果：
