P8666题解

一只小菜包 · 2024-04-07 17:08:20 · 题解

题意

这道题目是一个典型的三维差分问题，结合二分查找进行求解。题目的背景是在三体攻击下，地球人派出了 A\times B\times C 艘战舰以三维立方体的形式排列在太空中，每艘战舰有其生命值。给出若干次攻击，每次攻击指定一个立方体区域及对该区域内所有战舰造成的伤害值，求最少需要多少次攻击才能摧毁至少一艘战舰。

思路分析

三维差分：首先，我们需要一个有效的方法来处理每次攻击对战舰生命值的影响。~~三维差分就飞奔过来了~~，它能够在 O(1) 的时间内完成对一个立方体区域内所有点的更新。具体来说，对于每一次攻击，我们只需要在差分数组的对应立方体的角上进行加减操作。通过这种方式，我们可以在后续一次性计算出每艘战舰受到的总伤害。
二分查找：题目要求找到摧毁至少一艘战舰的最少攻击次数，自然我们想到使用二分查找。即在给定的攻击次数范围内寻找最小的满足条件的次数。对于二分查找的每一个中间值 mid ，我们检查前 mid 次攻击是否能摧毁至少一艘战舰，如果能，则说明答案可能在左半边，否则在右半边。

代码


#include <bits/stdc++.h>
#define ll long long
#define mem(a, m) memset(a, m, sizeof(a)); // 快速初始化数组的宏
using namespace std;

const int MAXN = 1e7 + 5; // 定义数组的最大长度
int shipA, shipB, shipC, numAttacks; // 分别存储战舰的层数A、行数B、列数C和攻击次数
int health[MAXN]; // 存储每艘战舰的生命值
int diff[MAXN]; // 差分数组，用于实现区间修改

// 攻击结构体，存储每次攻击的区间和伤害值
struct Attack {
    int startA, endA, startB, endB, startC, endC, damage;
} attacks[MAXN]; // 攻击数组，存储所有攻击的信息

// 三维坐标转换为一维索引的函数
int getIndex(int a, int b, int c) {
    return ((a - 1) * shipB + (b - 1)) * shipC + (c - 1) + 1;
}

// 检查函数，参数mid表示考虑前mid次攻击是否可以破坏某艘战舰
bool check(int mid) {
    mem(diff, 0); // 使用memset将差分数组初始化为0
    // 遍历前mid次攻击，更新差分数组
    for (int i = 1; i <= mid; i++) {
        // 提取第i次攻击的信息
        int la = attacks[i].startA, ra = attacks[i].endA;
        int lb = attacks[i].startB, rb = attacks[i].endB;
        int lc = attacks[i].startC, rc = attacks[i].endC;
        int h = attacks[i].damage;

        // 根据差分原理，对每个立方体的角进行更新
        diff[getIndex(la, lb, lc)] += h;
        diff[getIndex(ra + 1, lb, lc)] -= h;
        diff[getIndex(la, rb + 1, lc)] -= h;
        diff[getIndex(la, lb, rc + 1)] -= h;
        diff[getIndex(ra + 1, rb + 1, lc)] += h;
        diff[getIndex(ra + 1, lb, rc + 1)] += h;
        diff[getIndex(la, rb + 1, rc + 1)] += h;
        diff[getIndex(ra + 1, rb + 1, rc + 1)] -= h;
    }

    // 计算差分数组的前缀和，还原出每个位置受到的总伤害
    for(int a = 1; a <= shipA; a++) {
        for(int b = 1; b <= shipB; b++) {
            for(int c = 1; c <= shipC; c++) {
                int idx = getIndex(a, b, c);
                diff[idx] += diff[getIndex(a - 1, b, c)] + diff[getIndex(a, b - 1, c)] + diff[getIndex(a, b, c - 1)]
                            - diff[getIndex(a - 1, b - 1, c)] - diff[getIndex(a - 1, b, c - 1)] - diff[getIndex(a, b - 1, c - 1)]
                            + diff[getIndex(a - 1, b - 1, c - 1)];
                // 如果计算出的伤害值大于战舰的生命值，则返回true
                if(diff[idx] > health[idx]) return true;
            }
        }
    }
    return false; // 若所有战舰生命值均未降至零以下，返回false
}

int main() {
    ios::sync_with_stdio(false);
    // 读入战舰的层数、行数、列数和攻击次数
    cin >> shipA >> shipB >> shipC >> numAttacks;

    // 读入每艘战舰的生命值
    for(int a = 1; a <= shipA; a++) {
        for(int b = 1; b <= shipB; b++) {
            for(int c = 1; c <= shipC; c++) {
                cin >> health[getIndex(a, b, c)];
            }
        }
    }

    // 读入所有攻击的信息
    for(int i = 1; i <= numAttacks; i++) {
        cin >> attacks[i].startA >> attacks[i].endA >> attacks[i].startB >> attacks[i].endB >> attacks[i].startC >> attacks[i].endC >> attacks[i].damage;
    }

    // 使用二分查找确定最小的可以摧毁至少一艘战舰的攻击次数
    int left = 1, right = numAttacks;
    while(left < right) {
        int mid = (left + right) / 2;
        if(check(mid)) right = mid; // 如果mid次攻击可以摧毁战舰，则在左侧查找
        else left = mid + 1; // 否则在右侧查找
    }

    cout << left; // 输出结果
    return 0;
}

代码简解

代码中定义了一个 Attack 结构体来存储每次攻击的信息，包括攻击的区间和伤害值。 getIndex 函数用于将三维坐标转换为一维索引，简化数组操作。check 函数实现了上述的三维差分逻辑，用于判断给定次数的攻击是否能摧毁至少一艘战舰。

在 main 函数中，首先读入战舰的层数、行数、列数和攻击次数，然后读入每艘战舰的生命值以及所有攻击的信息。使用二分查找确定能够摧毁至少一艘战舰的最少攻击次数，并输出这个值。

注释里对代码的解释已经很详细了，建议完整地看完示范代码后再做题。