欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P1086 花生采摘

程序员文章站 2022-07-07 15:49:13
...

洛谷 P1086 花生采摘


这道题难点在于理解题意

只有第一次可以从路到田,最后一次从田到路

中间不能以回路再田的方式减少步数

剩下的就是来回步数的细节问题

顺序位置可以用结构体存了 没必要存二维数组

代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct pos
{
	int x, y;
	int val;
}arr[2500];

bool cmp(pos a, pos b)
{
	return a.val > b.val;
}

int main()
{
	int M, N, K, ft = 0, tmp;
	cin>>M>>N>>K;
	
	for(int i = 0; i < M; i++)
	{
		for(int j = 0; j < N; j++)
		{
			cin>>tmp;
			
			if(tmp != 0)
			{
				arr[ft].x = j;
				arr[ft].y = i;
				arr[ft++].val = tmp; 
			}
			
		}
	}
	
	sort(arr, arr + ft, cmp);
	
	int ans = 0;
	
	/*test
		1, 4
		3, 1
	*/
	
	for(int i = 0; i < ft; i++)
	{
		//cout<<arr[i].x<<' '<<arr[i].y<<' '<<arr[i].val<<endl;
		int ret = 0, py;
		
		py = arr[i].y + 1;
		
		if(i == 0)
		{			
			ret += arr[0].y + 2;
		}
		
		else
		{
			
			py = arr[i].y + 1;
			ret += abs(arr[i].x - arr[i - 1].x) + abs(arr[i].y - arr[i - 1].y) + 1;
		}
		
		if(K - (ret + py) < 0)
			break;
		else
		{
			K -= ret;
			ans += arr[i].val;
		}
				
	}
	
	cout<<ans<<endl;
	
	return 0;
}