花生采摘 题解

题目传送门

翻了这道题的前两页题解，没有几个和我的思路相仿的。唯一的一个我看不懂

首先为了让大家快速找到自己可能有的错误，把这道题的部分坑点给出来：

1. 关于算法，题目已经明确规定了走法是按照花生数目由大到小摘花生：

鲁宾逊先生说：“你$\color{red}\text{先找出花生最多}$的植株，去采摘它的花生；然后$\color{red}\text{再找出剩下的植株里花生最多的}$，去采摘它的花生；$\color{Blue}\text{依此类推}$，不过你一定要在我限定的时间内回到路边。”

2. 关于摘花生，将花生采摘下来是要耗费时间的。有同学没有+1，就会爆炸。

3. 关于抄近道，题目虽然没有说清楚，但是不能通过在大路上抄近道省时间。

比如这样的情况，不能走红线，只能老老实实走蓝色路（曼哈顿）

4. 关于第四个数据点：

1 1 5

15

如果你的答案是 45，请检查一下你是否重复在摘这个仅有的格子。

5. 关于数组大小：开25*25绝对不会错。

6. 对于没读好题目：保证没有花生数一样的格子，各位不要想太多。

7. 考虑最终答案是0的情况，不要一上来就摘了花生回不去。

8. 无脑抄袭我的代码或其他有反作弊措施的代码的人会体验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;

$j$表示花生数目，$x$和$y$分别为坐标，$w$表示已经消耗的时间。后文的$s$表示已经摘的花生数目。

每次+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;
   }

注意要判断队列是否为空，否则会$\color{Orange}\text{90}$分，$\color{Red}\text{WA}$第4个数据，原因是这篇文章开头写的第四点。

最终是各位期待的完整代码（相信很多人直接跳过，空降到这里来了吧……）

#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;
}

纯净无注释版本：

#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;
}