HDU 4415 Assassin's Creed：貪心策略優化殺敵順序

題目大意

• 袖劍耐久度 m，n 名士兵。
• 士兵 i：袖劍殺耗 A_i，獲得武器可殺 B_i 名其他士兵（不消耗耐久）。
• 目標：最大化殺敵數，其次最小化耐久消耗。

貪心分類與排序

1. 分兩組：
    E1：B_i = 0（無武器增益），按 A_i 升序。
    E2：B_i > 0，按 A_i 升序。
2. 觀察：若能袖劍殺掉 E2 中最小 A 的士兵，則可用其武器連鎖殺光所有 E2（武器數足夠）。
3. 基本策略：先嘗試殺光 E2（耗 minA_E2），剩餘耐久殺 E1 前綴；武器多餘時殺 E1 尾部大 A。
4. 反例發現：有時「用袖劍殺 E2 中較小 A，釋放武器殺 E1 大 A」更優。
5. 改進雙指針合併：
    維護 E1 指針 i（從小到大），E2 指針 j（從小到大，跳過首個）。
    每步比較 E1[i].A 與 E2[j].A：
     若 E1[i].A ≤ E2[j].A，用袖劍殺 E1[i]，i++。
     否則用袖劍殺 E2[j]（原本擬用武器殺），釋放武器殺 E1[i]，j++，i++（武器抵消一個 E1）。
    直到耐久不足或無敵人。

完整代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
ll e1[MAXN];
struct E2 { ll a, b; } e2[MAXN];
bool cmpE2(const E2& x, const E2& y) { return x.a < y.a; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        int n; ll m; cin >> n >> m;
        int c1 = 0, c2 = 0;
        for (int i = 0; i < n; ++i) {
            ll a, b; cin >> a >> b;
            if (b == 0) e1[c1++] = a;
            else e2[c2++] = {a, b};
        }
        sort(e1, e1 + c1);
        sort(e2, e2 + c2, cmpE2);

        // 方案 A：只殺 E1
        ll dur = m, killA = 0, costA = 0;
        for (int i = 0; i < c1 && dur >= e1[i]; ++i) {
            dur -= e1[i]; costA += e1[i]; ++killA;
        }

        // 方案 B：殺 E2 + 混合
        ll killB = 0, costB = 0;
        if (c2 > 0 && e2[0].a <= m) {
            dur = m - e2[0].a;
            costB = e2[0].a;
            killB = 1;
            ll weapons = e2[0].b;
            for (int i = 1; i < c2; ++i) weapons += e2[i].b, ++killB, costB += e2[i].a; // 這裡簡化，實際需雙指針
            // 完整雙指針邏輯見下方
        }

        // 完整雙指針合併殺敵
        auto solveMix = [&](ll dur) -> pair {
            ll cost = 0, kill = 0;
            int i = 0, j = 1; // e2[0] 已用袖劍殺
            ll weapons = 0;
            for (int k = 0; k < c2; ++k) weapons += e2[k].b;
            weapons -= c2; // 扣除殺 E2 自身消耗的武器
            // 先用武器殺盡可能多的 E1 尾部
            int e1Left = c1;
            while (e1Left > 0 && weapons > 0) { --e1Left; --weapons; ++kill; }
            // 再雙指針處理剩餘 E1[0..e1Left-1] 和 E2[1..c2-1]
            while (i < e1Left && (j < c2 || dur >= e1[i])) {
                bool useE1 = (j >= c2) || (dur >= e1[i] && e1[i] <= e2[j].a);
                if (useE1) {
                    if (dur < e1[i]) break;
                    dur -= e1[i]; cost += e1[i]; ++kill; ++i;
                } else {
                    if (dur < e2[j].a) break;
                    dur -= e2[j].a; cost += e2[j].a; ++kill; ++j; ++i; // 武器殺一個 E1
                }
            }
            return {kill, cost};
        };

        pair best = {killA, costA};
        if (c2 > 0 && e2[0].a <= m) {
            auto cand = solveMix(m - e2[0].a);
            cand.first += 1; // 算上 e2[0]
            cand.second += e2[0].a;
            if (cand.first > best.first || (cand.first == best.first && cand.second < best.second))
                best = cand;
        }

        cout << "Case " << cs << ": " << best.first << " " << best.second << "\n";
    }
    return 0;
}

關鍵點總結

• 將問題轉化為：袖劍耐久度分配給「直接殺」與「殺 E2 釋放武器」兩類動作。
• 雙指針合併兩條已排序序列，每步選擇當前耐久消耗較小者，實現全局最優。
• 時間 O(n log n)，空間 O(n)。