2022.3.27网易后端暑期实习笔试题解（转载）

原地址：

https://www.nowcoder.com/discuss/914908?type=2&order=1&pos=1&page=1&source_id=discuss_tag_nctrack&channel=-1&ncTraceId=86d5e3c9b08940e9a6d5b097f01013f5.5213.16484321639607538&gio_id=06E2CF046AA2F56D5FDD460AAFF09D05-1648432163787

个人加注释：

1.编程题第一题：小红杀怪

方法一：枚举

思路：枚举使用烈焰风暴（群体技能）的次数，然后可以O(1)算出需要使用火球术（单体技能）的次数。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x, y, a, b, i; // 这里x和y是血量，a和b是技能伤害
    cin >> x >> y >> a >> b;
    int ma = 1e9;
    for (i = 0; i <= 1e6; i++)
    {
        int c1 = 0, c2 = 0;
        if ((x - i * b) > 0)
            c1 = max(c1, (x - i * b) / a + ((x - i * b) % a != 0));
        if ((y - i * b) > 0)
            c2 = max(c2, (y - i * b) / a + ((y - i * b) % a != 0));
        ma = min(ma, i + c1 + c2);
    }
    cout << ma;
}

方法二：贪心（根据x和y的大小关系进行分类讨论）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x, y, a, b, i;
    cin >> a >> b >> x >> y; // 这里a和b是血量，x和y是技能伤害
    if (y >= max(a, b))
        cout << 1;
    else if (y > x) // 群体技能比单体技能伤害还要高
    {
        a = max(a, b);
        // (a % y != 0) == 0 表示a / y除尽了，加0；== 1 表示还需要用一次技能，则加1（下同）
        cout << a / y + (a % y != 0);
    }
    else if (x > 2 * y) // 单体技能伤害量超过群体伤害的两倍（两个怪），此时分别使用数次单体技能
    {
        cout << a / x + b / x + (a % x != 0) + (b % x != 0);
    }
    else // y <= x <= 2 * y
    {
        if (a > b) swap(a, b); // 使得下叙的a <= b
        int cnt = a / y + (a % y != 0); // 首先对较少血量的a使用多少次群体技能
        b -= y * cnt; // 因为是群体技能，所以b也减少了这么多血量
        cout << b / x + (b % x != 0) + cnt; // b剩下了的血量用单体技能，加上cnt就是答案
    }
    return 0; // 本人加上
}

4.编程题第四题：小红闯沼泽地

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;

const int dx[] = {1, 0, 0}; // 定义dx，dy偏移量;
const int dy[] = {0, 1, -1}; // {1, 0}为下，{0, 1}为右，{0, -1}为上
const int N = 503;

struct Node
{
    int x, y, w;
    bool operator<(const Node &b) const { return w > b.w; } // 比较函数
};

int n, m;
int a[N][N];
priority_queue<Node> q; // 优先队列是按w小的优先出队
int d[N][N];
bool vis[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> a[i][j]; // 构造地图
        }
    }
    memset(d, 0x3f, sizeof(d));
    d[1][1] = 0;
    q.push({1, 1});
    while (q.size())
    {
        int x = q.top().x, y = q.top().y;
        q.pop();
        if (vis[x][y])
            continue;
        vis[x][y] = true;
        for (int i = 0; i < 3; ++i)
        {
            int tx = dx[i] + x, ty = dy[i] + y;
            int w = (a[x][y] ^ a[tx][ty]) ? 2 : 1; // 用异或操作得到跨越两块区域所花的时间
            if (tx && ty && tx <= n && ty <= m) // 点{tx, ty}没有出界
            {
                if (d[tx][ty] > d[x][y] + w) // dijstra中的更新距离方法，贪心保证最短距离
                {
                    d[tx][ty] = d[x][y] + w;
                    q.push((Node){tx, ty, d[tx][ty]});
                }
            }
        }
    }
    cout << d[n][m] << endl;
    return 0;
}