H题 #时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学#

题目描述

给出一个矩阵的敌人，每次向一个地点增援，寻找使13个方格的菱形范围内敌人最多的中心点。

思路

最开始是用dx和dy储存13个偏移量，每次检查更新以“以增援地为中心的菱形范围内的地点”为中心的菱形，这样每次更新查找13个点即可，但是写起来很麻烦，要实时记录最大值，用set会更方便。这时候就能发现，敌人会增加，最大值不会变小，所以直接记录最大值即可。题解提到如果会变小就不适用了，那我们就需要动态维护全局最大值，貌似可以用优先队列，每次增援压到堆中，再从堆顶把过期的弹出。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> a(n, vector<long long>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];

    const int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
    const int dy[13] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};
	// 每个方格作为中心时的初始总敌人数
    vector<vector<long long>> c(n, vector<long long>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long sum = 0;
            for (int k = 0; k < 13; k++) {
                int ni = i + dx[k], nj = j + dy[k];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m)
                    sum += a[ni][nj];
            }
            c[i][j] = sum;
        }
    }
	//初始最大值
    long long max_val = -1;
    int max_i = 0, max_j = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (c[i][j] > max_val) {
                max_val = c[i][j];
                max_i = i;
                max_j = j;
            }

    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        --x; --y;

        for (int k = 0; k < 13; k++) {
            int ni = x + dx[k], nj = y + dy[k];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                c[ni][nj] += z;
                if (c[ni][nj] > max_val) {
                    max_val = c[ni][nj];
                    max_i = ni;
                    max_j = nj;
                }
            }
        }

        cout << max_i + 1 << ' ' << max_j + 1 << '\n';
    }
    return 0;
}