牛客NOIP暑期七天营-普及组4-C火龙果田

题目大意：n*m矩阵，某些位置已经有一个数字，其他位置如何填，才能使数字之和最大？要求相邻两个数字之差不超过d。

要数字之和最大，填的数字越大越好。

对于一个空格，到底填多少呢？一时很难确定。

对于最小的数字a，周围填的数字越大越好，那就填a+d吧！填下去之后，如果与周围有冲突，那就填不了了：

1、如果周围原来是空的，那么这个数字不比a小，他之前的数字也不比a小，不可能发生冲突呢？

2、如果周围原来有预置的数字，那没办法了，因为他肯定是非常大的一个数，已经用最大的填也填不了。

大概就是这样，需要注意的是，输入数据允许重复，但不允许重复位置不同数值，而且数据有0。

方法一，用优先队列（堆）快速找到最小值，填周围的数字，时间复杂度，感觉比较容易超时。

#include <bits/stdc++.h>
using namespace std;
int F, S, D, c, n, m, i, j, k, ans, mo = 1e9 + 7;
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
int x, y, z, xx, yy, zz, mp[1005][1005], f[1005][1005];
struct XY{
    int x, y, z;
    bool operator < (const XY &A) const{
        return z > A.z;
    }
} t;
priority_queue <XY> q;
int ok(int x, int y, int z){
    if(x < 1 || x > n || y < 1 || y > m) return 0;
    if(f[x][y]) return 0;
    f[x][y] = 1;//避免零美味程度 
    int i, xx, yy;
    for(i=0; i<4; i++){
        xx = x + dx[i], yy = y + dy[i];
        if(f[xx][yy]){
            F |= abs(z-mp[xx][yy]) > D;
        }
    }
    return F == 0;
}
int main(){
    scanf("%d%d%d%d", &n, &m, &c, &D);
    for(i=1; i<=c; i++){
        scanf("%d%d%d", &x, &y, &z);
        if(f[x][y] && mp[x][y]!=z) F = 1;//输入数据允许重复 
        if(ok(x, y, z)) q.push((XY){x, y, mp[x][y] = z});
    }
    while(F==0 && q.size()){
        t = q.top(), q.pop();
        x = t.x, y = t.y, z = t.z, S++, ans = (ans+z)%mo;
        for(i=0; i<4; i++){
            xx = x+dx[i], yy = y+dy[i], zz = z+D;
            if(ok(xx, yy, zz)){
                q.push((XY){xx, yy, mp[xx][yy] = zz});
            }
        }
    }
    if(F == 0 && S == m*n) printf("%d\n", ans);
    else printf("PitayaCrying\n");
    return 0;
}

方法二：原来的2000多个数据先排序，后面填的数字必然单调递增，用单调队列，时间复杂度。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int F, S, D, c, n, m, i, j, k, ans, mo = 1e9 + 7;
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
int x, y, z, xx, yy, zz, mp[N][N], f[N][N];
int da, db, qa, qb;
struct XY{
    int x, y, z;
    bool operator < (const XY &A) const{
        return z < A.z;
    }
} d[N*2], q[N*N], t;
int ok(int x, int y, int z){
    if(f[x][y]) return 0;//填过不再填 
    if(x < 1 || x > n || y < 1 || y > m) return 0;
    int i, xx, yy;
    for(i=0; i<4; i++){
        xx = x + dx[i], yy = y + dy[i];
        if(f[xx][yy]){
            F |= abs(z-mp[xx][yy]) > D;
        }
    }
    f[x][y] = 1;
    return F == 0;
}
int main(){
    scanf("%d%d%d%d", &n, &m, &c, &D);
    for(i=1; i<=c; i++){
        scanf("%d%d%d", &x, &y, &z);
        if(f[x][y] && mp[x][y]!=z) F = 1;//输入数据允许重复
        if(ok(x, y, z)) d[++db] = (XY){x, y, mp[x][y] = z};
    }
    sort(d+1, d+db+1);
    da = qa = 1;
    while(F==0 && (da<=db || qa<=qb)){
        if(da > db) t = q[qa++];
        else if(qa > qb) t = d[da++];
        else if(d[da] < q[qa]) t = d[da++];
        else t = q[qa++];
        x = t.x, y = t.y, z = t.z, S++, ans = (ans+z)%mo;
        for(i=0; i<4; i++){
            xx = x+dx[i], yy = y+dy[i], zz = z+D;
            if(ok(xx, yy, zz)){
                q[++qb] = (XY){xx, yy, mp[xx][yy] = zz};
            }
        }
    }
    if(F == 0 && S == m*n) printf("%d\n", ans);
    else printf("PitayaCrying\n");
    return 0;
}