题目分析

问题简述

有 $n$ 个敌人，每个敌人有三个属性 $(a_i, b_i, c_i)$ 分别表示臭度、绿度和丑度。你初始有力量 $X$ 和紫度 $Y$，满足：

• 紫度 $Y$ 固定不变
• 击败敌人 $i$ 需要 $X \geq a_i$ 且 $Y \geq b_i$
• 击败敌人 $i$ 后，$X$ 增加 $c_i$

求初始 $X+Y$ 的最小值，使得能够击败至少 $k$ 个敌人。

关键观察

1. 紫度约束：由于 $Y$ 固定不变，我们只能击败那些 $b_i \leq Y$ 的敌人
2. 力量增长：击败敌人后力量 $X$ 会增加，这会影响后续能击败的敌人
3. 选择顺序：击败顺序很重要，应该优先击败那些要求力量小但提供力量增长多的敌人

解法思路

方法：二分答案 + 贪心验证

步骤1：二分答案

我们二分 $X+Y$ 的值，对于每个候选值 $S$，我们需要验证是否存在 $X$ 和 $Y$ 满足：

• $X + Y = S$
• $X \geq 0, Y \geq 0$
• 能够击败至少 $k$ 个敌人

步骤2：验证函数

对于给定的 $S$，我们枚举所有可能的 $Y$ 值（实际上只需要考虑敌人的 $b_i$ 值作为候选），对于每个 $Y$：

1. 筛选出所有 $b_i \leq Y$ 的敌人
2. 初始力量 $X = S - Y$
3. 使用贪心策略选择击败顺序

步骤3：贪心策略

对于当前可击败的敌人集合，我们应该：

1. 优先击败那些 $a_i \leq$ 当前力量 $X$ 的敌人
2. 在这些敌人中，优先击败那些 $a_i$ 较小且 $c_i$ 较大的敌人

具体实现可以使用堆（优先队列）：

• 维护当前可击败的敌人集合（$a_i \leq X$）
• 每次选择 $a_i$ 最小的敌人击败（因为要求 $X \geq a_i$）
• 击败后 $X$ 增加 $c_i$，可能解锁新的敌人

代码实现

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

typedef long long ll;
const int MAXN = 200005;

struct Enemy {
    ll a, b, c;
} enemies[MAXN];

int n, k;

// 检查对于给定的Y，初始力量X是否能击败至少k个敌人
bool check_for_Y(ll X, ll Y) {
    // 筛选出所有b_i <= Y的敌人
    vector<Enemy> candidates;
    for (int i = 0; i < n; i++) {
        if (enemies[i].b <= Y) {
            candidates.push_back(enemies[i]);
        }
    }
    
    // 按a_i排序
    sort(candidates.begin(), candidates.end(), [](const Enemy& x, const Enemy& y) {
        return x.a < y.a;
    });
    
    priority_queue<pair<ll, ll>> pq; // 存储(c_i, a_i)，按c_i大顶堆
    
    ll current_power = X;
    int idx = 0;
    int defeated = 0;
    
    while (defeated < k) {
        // 将所有a_i <= current_power的敌人加入堆
        while (idx < candidates.size() && candidates[idx].a <= current_power) {
            pq.push({candidates[idx].c, candidates[idx].a});
            idx++;
        }
        
        if (pq.empty()) {
            return false; // 没有可击败的敌人
        }
        
        // 击败提供c_i最大的敌人
        auto [c_val, a_val] = pq.top();
        pq.pop();
        current_power += c_val;
        defeated++;
    }
    
    return true;
}

// 检查是否存在Y使得初始力量S-Y能击败至少k个敌人
bool check(ll S) {
    // 收集所有可能的Y候选值（敌人的b_i）
    vector<ll> candidate_Y;
    for (int i = 0; i < n; i++) {
        candidate_Y.push_back(enemies[i].b);
    }
    // 添加0和可能的最小值
    candidate_Y.push_back(0);
    sort(candidate_Y.begin(), candidate_Y.end());
    candidate_Y.erase(unique(candidate_Y.begin(), candidate_Y.end()), candidate_Y.end());
    
    // 对于每个候选Y，检查对应的X = S - Y是否可行
    for (ll Y : candidate_Y) {
        if (Y > S) continue; // Y不能大于S
        ll X = S - Y;
        if (X < 0) continue;
        
        if (check_for_Y(X, Y)) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> enemies[i].a >> enemies[i].b >> enemies[i].c;
    }
    
    // 二分答案
    ll left = 0, right = 2e18; // 上界设的足够大
    ll answer = right;
    
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

复杂度分析

• 二分答案：$O(\log (10^9))$ 次迭代
• 验证函数：
  • 收集候选Y：$O(n)$
  • 对于每个候选Y：
    • 筛选敌人：$O(n)$
    • 排序：$O(n \log n)$
    • 贪心过程：$O(n \log n)$
• 总复杂度：$O(n^2 \log^2 n)$（需要优化）

优化版本

上面的实现对于大数据会超时，我们需要优化：

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

typedef long long ll;
const int MAXN = 200005;

struct Enemy {
    ll a, b, c;
} enemies[MAXN];

int n, k;

// 优化版本：一次性处理所有候选Y
bool check(ll S) {
    // 按b_i排序敌人
    vector<int> indices(n);
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin(), indices.end(), [](int i, int j) {
        return enemies[i].b < enemies[j].b;
    });
    
    // 双指针 + 堆
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> available; // 最小堆，按a_i排序
    
    ll current_power = 0;
    int defeated = 0;
    int ptr = 0;
    
    // 枚举Y值（即敌人的b_i）
    for (int i = 0; i < n; i++) {
        ll Y = enemies[indices[i]].b;
        if (Y > S) break;
        
        ll X = S - Y;
        if (X < 0) continue;
        
        // 添加所有b_i <= Y的敌人到可用集合
        while (ptr < n && enemies[indices[ptr]].b <= Y) {
            available.push({enemies[indices[ptr]].a, enemies[indices[ptr]].c});
            ptr++;
        }
        
        // 贪心选择
        priority_queue<ll> pq; // 大顶堆，存储当前可击败敌人的c_i
        current_power = X;
        defeated = 0;
        
        vector<pair<ll, ll>> temp;
        while (defeated < k && (!available.empty() || !pq.empty())) {
            // 将可击败的敌人加入堆
            while (!available.empty() && available.top().first <= current_power) {
                pq.push(available.top().second);
                available.pop();
            }
            
            if (pq.empty()) break;
            
            // 击败提供c_i最大的敌人
            current_power += pq.top();
            pq.pop();
            defeated++;
        }
        
        // 恢复available队列
        while (!available.empty()) {
            temp.push_back(available.top());
            available.pop();
        }
        for (auto p : temp) {
            available.push(p);
        }
        
        if (defeated >= k) {
            return true;
        }
    }
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> enemies[i].a >> enemies[i].b >> enemies[i].c;
    }
    
    ll left = 0, right = 4e18;
    ll answer = right;
    
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

算法总结

1. 二分答案：在可能的值域范围内二分查找最小的 $X+Y$
2. 贪心验证：对于每个候选值，枚举可能的 $Y$，然后用贪心策略验证
3. 堆优化：使用堆来高效选择当前最优的敌人击败
4. 双指针：按 $b_i$ 排序后使用双指针维护当前可用的敌人集合

关键点

• 紫度 $Y$ 固定后，问题转化为一维的动态贪心问题
• 击败顺序很重要：应该优先击败要求低但回报高的敌人
• 使用堆数据结构可以高效维护当前最优选择

这个解法的时间复杂度为 $O(n \log n \log A)$，其中 $A$ 是答案的值域范围，能够通过所有测试数据。