3518749_ac_16ms_240k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;

class pos
{
public:
	int x, y, num;
	pos(int _x, int _y, int _num)
	{
		x = _x;
		y = _y;
		num = _num;
	}
	pos()
	{
	}
	bool operator < (const pos p)	const
	{
		return num > p.num;
	}
};

vector <pos> peanuts;
vector <pos> ::iterator ip;

void input()
{
	int num;

	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &num);
			peanuts.push_back(pos(i, j, num));
		}
	}
	sort(peanuts.begin(), peanuts.end());
}

int f(int num)
{
	return num < 0 ? -num : num;
}

int dis(int x1, int y1, int x2, int y2)
{
	return f(x1 - x2) + f(y1 - y2);
}

int solve()
{
	int total (0), t (0), ret (0);
	int lastx, lasty;
	pos now;

	if (peanuts.size() == 0)
	{
		return 0;
	}
	lastx = -1;
	lasty = (*peanuts.begin()).y;
	for (ip = peanuts.begin(); k > 0 && ip != peanuts.end(); ++ip)
	{
		now = *ip;
		t += dis(lastx, lasty, now.x, now.y) + 1 ;
		lastx = now.x;
		lasty = now.y;
		if (t + now.x + 1 <= k)
		{
			ret += now.num;
		}
		else
		{
			break;
		}
	}
	return ret;
}

int main()
{
	int cas;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		peanuts.clear();
		input();
		printf("%d\n", solve());
	}
	return 0;
}