【题解】P4624 采矿

幽灵特工 · 2021-09-15 17:27:17 · 题解

本文写于2021年7月23日，时正星际争霸2人族名将吕布退役。

白门楼倒了。

小学生秒懂系列。

欢迎进入 blog 查看你的小学生秒懂系列都更新了啥。

前言

最初是今年六月份看见这题的，当时就想，这么简单一爆搜我半小时就能搞定！现在（9月15）我知道我错了，但也许错的不是我。

经过与诸多大佬的讨论，查阅了多方资料，我们认定本题数据有误。例如对于样例输入，网上就有30和40两种不同的样例输出，在此不讨论哪种输出是正确的。这篇文章只能给出我的思路及代码供参考，由于测试数据版本众多故不保证代码完全正确。

经过这三个月的深思熟虑，我决定写下这篇文章，同时有把握保证下附的代码能通过大部分数据。

思路

显然是搜索题。

本题可以使用以下贪心策略辅助搜索：优先采集晶体矿，同时尝试建造农民。

对于搜索过程，定义搜索状态包含以下内容：

晶体矿储量（题中名称为冰矿，因为游戏中晶体矿看起来很像冰）
高能瓦斯储量（题中名为气矿，因为所有星际玩家都这么称呼它）
当前时间
SCV总量
将要得到的晶体矿收入
将要得到的高能瓦斯收入
事件优先队列

定义事件包含以下内容：

事件结束时间
事件类型（采集晶体矿，采集高能瓦斯，建造SCV其中之一）
一共有几个SCV在执行此事件。可以为0。
重载运算符 <，按事件结束时间为优先队列（小根堆）提供排序依据。

程序中执行以下 BFS 搜索过程：

处理状态。已处理过的状态出队。
新状态入队。具体是何种状态请见代码。
如果队列空，搜索结束。

搜索注意最优性剪枝，否则T飞。

#include <bits/stdc++.h>
using namespace std;
int t1, t2, t3, p1, p2;

struct work {//事件
    int time, type, SCV;//事件结束时间，事件类型（采气或采钱，训练SCV），一共几个工人在采集
    work(int a, int b, int c) {
        time = a; type = b; SCV = c;
    }
    bool operator < (work x)const {
        return this->time > x.time;
    }
};

struct SC {//StarCraft，星际争霸
    int Minerals, Vespene_Gas;//晶体矿储量，高能瓦斯储量
    int Time;//中国第一t理赔难（乱入了，其实是当前时间）
    int MineralsWill, Vespene_GasWill;//将要得到的收入
    int SCV;//SCV总量，不管空闲与否
    priority_queue <work> pq;
    SC(int x, int y, int a, work b, int n, int m, int scv) {
        Minerals = x; Vespene_Gas = y;
        Time = a;
        pq.push(b);
        MineralsWill = n; Vespene_GasWill = m;
        SCV = scv;
    }
};
queue <SC> q;
int bfs() {
    int ans = 1e9 + 10;
    q.push(SC(50, 0, 0, work(0, -1, 4), 0, 0, 4));
    while (!q.empty()) {
        SC sc = q.front();
        q.pop();
    sametimework:;
        int SCV = sc.pq.top().SCV;
        sc.Time = sc.pq.top().time;
        switch (sc.pq.top().type) {
        case -1:break;
        case 1: {sc.Minerals += SCV * 8; sc.MineralsWill -= SCV * 8; break; }
        case 2: {sc.Vespene_Gas += SCV * 8; sc.Vespene_GasWill -= SCV * 8; break; }
        case 3: {SCV++; sc.SCV++; }
        }
        sc.pq.pop();
        if (!sc.pq.empty() && !q.empty())if (sc.pq.top().time == sc.Time)goto sametimework;//同时完成的事件顺手做掉
        //接下来开始新事件
        if (sc.Time >= ans)continue;
        if (sc.Minerals >= p1 && sc.Vespene_Gas >= p2) {
            ans = sc.Time;
            continue;
        }
        if (sc.Minerals + sc.MineralsWill >= p1) {//钱够了
            if (sc.Vespene_Gas + sc.Vespene_GasWill >= p2)continue;//气也够了
            sc.pq.push(work(sc.Time + t2, 2, SCV));
            sc.Vespene_GasWill += SCV * 8;
            q.push(sc);//不造农民，全部采气
            if (sc.Minerals < 50)continue;
            if (sc.SCV * 8 * t2 >= p2)continue;
            sc.Minerals -= 50;
            sc.pq.push(work(sc.Time + t3, 3, 0));
            q.push(sc);//造个农民，全部采气
            //cout << 1 << endl;
            continue;
        }
        if (sc.Vespene_Gas + sc.Vespene_GasWill >= p2)continue;//气也够了
        else {
            int x = min(SCV, (p1 - sc.Minerals - sc.MineralsWill + 7) / 8);//再有x个农民采钱就ok了
            sc.pq.push(work(sc.Time + t1, 1, x));
            if (SCV > x)sc.pq.push(work(sc.Time + t2, 2, SCV - x));
            sc.MineralsWill += x * 8;
            sc.Vespene_GasWill += (SCV - x) * 8;
            q.push(sc);//不造农民，进行采集
            if (sc.Minerals < 50)continue;
            if (sc.SCV * 8 * t1 >= p1)continue;
            if (sc.SCV * 8 * t2 >= p2)continue;
            sc.Minerals -= 50;
            sc.pq.push(work(sc.Time + t3, 3, 0));
            q.push(sc);//造个农民，进行采集
            //cout << 1 << endl;
        }
    }
    return ans;
}
int main()
{
    cin >> t1 >> t2 >> t3 >> p1 >> p2;
    cout << bfs();
}