三小时四道题。游戏服务端工程师。

A: 100%

签到题。

模拟。

B: 82%

输入：n个任务，m天，n个任务的value和截止日期limit，m天中每天发放多少张券。一张券可以完成一个任务。

输出：最多能获得多少value。

贪心。

笔试后完善的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    // 2. value相同时，日期大的排前面
    // why? 获得一个相同的value，使用后面发的券更“优惠”（前面的券能cover的任务范围更大）
    if (a.first == b.first)
        return a.second < b.second; 
    // 1. value大的排前面
    return a.first > b.first;       
}

int main() {
    int n, m;       // m, n <= 1e6
    cin >> n >> m;
    vector<pair<int, int>> tasks;
    for (int i = 0; i < n; ++i) {
        int value, limit;
        cin >> value >> limit;
        tasks.push_back({value, limit});
    }
    sort(tasks.begin(), tasks.end(), cmp);

    vector<int> tickets(m + 1);
    for (int i = 1; i <= m; ++i) { // 第i天
        cin >> tickets[i];
    }

    // 贪心算法，先把分数最高的任务（同分数以日期最高排序）和离截止日期最近的券匹配 
    long long ans = 0;
    int start = 1; // start之前没有券了
    for (int i = 0; i < tasks.size() && start <= m; ++i) {
        int value = tasks[i].first, day = min(tasks[i].second, m);

		// 极端情况下，每次都要遍历 m 次，这样就会超时。
		// 考虑用map<天数，券数>存储tickets，删除券数为0的元素。
        while (day >= start && tickets[day] == 0) --day;
        if (day >= start) {
            --tickets[day];
            ans += value;
        }
        else
            start = tasks[i].second + 1;
    }
    cout << ans << endl;
    return 0;
}

/*
4 3
3 1
4 2
5 3
6 4
1
1
1
*/

C: 100%

PI和老虎要离开无人岛去漂流，出发前要准备食物和水。PI每天需要1份食物和2份水，老虎每天需要2份食物和1份水。船上的体积为x，食物n份，水m份，n + 3m <= x。PI和老虎都不能中断饮食，PI在断食后Q天死亡，老虎在断食后P天吃掉PI。

输入x、P、Q，输出PI最久能存活的天数。

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

int main()
{   
    int x, P, Q;
    cin >> x >> P >> Q;
    // pi吃一天需要1+3*2=7
    // 老虎吃一天需要1*2+3=5
    // 两者都吃一天需要12
    long long ans = 0;

    int diffDay = abs(P - Q), supply = 7;
    if (P < Q)
        supply = 5;
    if (x < diffDay * supply)
        ans = x / supply + min(P, Q);
    else
        ans = (x - diffDay * supply) / 12 + max(P, Q);

    // if (P > Q) {
    //     if (x < (P - Q) * 7) {
    //         ans = x / 7 + Q;
    //     }
    //     else {
    //         x -= (P - Q) * 7;
    //         ans = x / 12 + P;
    //     }
    // }
    // else {
    //     if (x < (Q - P) * 5) {
    //         ans = x / 5 + P;
    //     }
    //     else {
    //         x -= (P - Q) * 5;
    //         ans = x / 12 + Q;
    //     }
    // }

    return 0;
}

D: 26%

n个量子台（每个量子台只能踏足一次），m个双向传送门（传送一次需要承受一定伤害w）。从 s 出发，到 e 取钥匙，然后到 t 回到现实世界。

如果能回到现实世界，输出最小的承受伤害；否则输出-1。

改善思路：最短路路径一定完整包含一条 s->e 最短，或者 e->t 最短（未证明）。实现时，分别找出 s->e（e->t）的最短路（可能不止一条），然后再找对应剩余图中的 e->t（e->s）的最短路，遍历这些组合。

不ac的代码（错误原因：只保存了到达某个点的最小距离，但最小不一定最好（路径不一样，对后续有影响），而且可能有多个最小）：

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 从 s 出发，到 e 取钥匙，然后到 t 回到现实世界
    // 每个量子台只能踏足一次
    int n, m, s, e, t;
    cin >> n >> m >> s >> e >> t;

    vector<vector<pair<int, int>>> edges(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // u,v ∈ [1, n]
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
    }

    // st[i]表示到达点i承受的（最小）伤害，-1表示还没到达
    // st[i][0]未经过e st[i][1]经过e 
    vector<vector<long long>> st(n + 1, vector<long long>(2, -1));
    queue<tuple<int, long long, vector<bool>>> q; // <当前到达的量子台，已承受的伤害，vis数组>
    st[s][0] = 0;
    vector<bool> vis(n + 1, false);
    vis[s] = true;
    q.push({s, 0, vis});
    while (!q.empty()) {
        auto tu = q.front(); q.pop();
        int pos = get<0>(tu);
        long long ww = get<1>(tu);

        for (auto x : edges[pos]) {
            vector<bool> v = get<2>(tu);
            int nextPos = x.first;
            if (v[nextPos]) continue;
            v[nextPos] = true;
            
            if (!v[e] && (st[nextPos][0] == -1 || ww + x.second < st[nextPos][0])) {
                st[nextPos][0] = ww + x.second;
                q.push({nextPos, st[nextPos][0], v});
            }
            if (v[e] && (st[nextPos][1] == -1 || ww + x.second < st[nextPos][1])) {
                st[nextPos][1] = ww + x.second;
                q.push({nextPos, st[nextPos][1], v});
            }
        }
    }
    cout << st[t][1] << endl;
    return 0;
}

/*
5 7 1 4 5
1 2 5
1 3 1
4 2 6
5 4 14
3 4 2
1 5 6
5 3 3
*/