解题思路

问题分析 贪心策略：多多必须按花生数量从多到少的顺序采摘，因此首先需要将所有非零花生的点按数量降序排序。 时间计算： 从道路到第一个点的时间为：行号 + 1（走到点的时间） + 1（采摘时间）。 从当前点到下一个点的时间为：两点之间的曼哈顿距离 + 1（采摘时间）。 最后从最后一个点返回道路的时间为：行号 + 1（走到道路的时间）。 终止条件：在每一步选择是否采摘当前点，若总时间超过 K，则停止采摘。 关键步骤 收集非零花生点：遍历网格，收集所有花生数量大于 0 的点，并记录其坐标和数量。 排序：按花生数量降序排序这些点。 模拟采摘过程： 初始化总时间为 0，总花生数为 0，上一个点为道路（行号为 0，列号任意，这里设为 0）。 遍历排序后的点，计算从当前位置到该点的时间，加上采摘时间和返回时间，判断是否超过 K。 若时间允许，累加花生数量和时间，更新上一个点为当前点；否则，终止循环。 #include #include #include #include #include using namespace std; const int MaxL = 2510;

struct Peanut { int x, y; int cnt; }peanuts[MaxL];

bool cmp(const Peanut& a, const Peanut& b) { if(a.cnt != b.cnt) { return a.cnt > b.cnt; }else if(a.x != b.x){ return a.x < b.x; }else{ return a.y < b.y; } }

int p_num; // 有 peanut 的点的总数 int t, m, n, k;

void solve() { sort(peanuts, peanuts + p_num, cmp); int ans = 0, time; if(peanuts[0].x * 2 + 1 > k) //花费的总时间大于 k { printf("0\n"); return; } ans += peanuts[0].cnt; time = 1 + peanuts[0].x; for(int i = 1; i < p_num; ++i) { if(time + abs(peanuts[i].x - peanuts[i - 1].x) + abs(peanuts[i].y - peanuts[i - 1].y) + 1 + peanuts[i].x <= k) { ans += peanuts[i].cnt; time += abs(peanuts[i].x - peanuts[i - 1].x) + abs(peanuts[i].y - peanuts[i - 1].y) + 1; }else{ break; } } printf("%d\n", ans); }

int main() { scanf("%d", &t); int a; while(t--) { p_num = 0; scanf("%d%d%d", &m, &n, &k); for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) { scanf("%d", &a); if(a) { peanuts[p_num].x = i, peanuts[p_num].y = j; peanuts[p_num++].cnt = a; } } } solve(); } return 0; }