OI赛制下的求解-打游戏(game.cpp)

Question

【题目描述】
你正在打游戏。
要想通关，你需要消灭 n 个敌人（编号为 1 ~ n）。
消灭第 i 个敌人的过程会消耗你 ai 点的血量，但消灭它之后，你会得到 bi 点的血量回升。
初始时，你有 s 点血量。在任意时刻，你的血量不能为零或为负。
问：如何安排消灭敌人的顺序，可以使得游戏顺利通关？
【输入格式】
第一行：包含两个整数 n, s。
接下来 n 行，每行包含两个整数 ai, bi。
【输出格式】
输出只有一行：

• 如果不存在合理的方案，输出一个整数 -1
• 否则输出一行 n 个数，表示你依次消灭的敌人的编号，数与数之间以一个空格隔开。如果存在多种方案，你只需要输出任意一种即可。
  【样例 1 输入】
  3 6
  3 1
  7 7
  2 8
  【样例 1 输出】
  1 3 2
  【样例 2 输入】
  3 6
  6 1
  7 7
  2 3
  【样例 2 输出】
• 1
  【数据规模】
  约 15% 的数据，1 ≤ n ≤ 10
  100% 的数据，1 ≤ n, s ≤ 10^5， 0 ≤ ai, bi ≤ 10^5

我的代码有错吗/？

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Node{
    int i;
    int a, b;
} ph[N], hp[N];

int n, s;
int res[N];

bool cmp1(Node a, Node b){
    return a.a < b.a;
}

bool cmp2(Node a, Node b){
    return a.b > b.b;
}

int main(){
    int cnt1 = 0, cnt2 = 0;
    cin >> n >> s;
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        if(b >= a){//有益
            ph[i] = {i, a, b};
            cnt1++;
        }else{
            hp[i] = {i, a, b};
            cnt2++;
        }
    }
    
    sort(hp + 1, hp + 1 + cnt1, cmp1);
    sort(ph + 1, ph + 1 + cnt2, cmp2);
    
    int hhp = s;
    for(int i = 1; i <= cnt1; i++){
        if(hhp <= ph[i].a){
            cout << -1;
            return 0;
        }
        hhp = hhp + ph[i].b - ph[i].a;
        res[i] = ph[i].i;
    }
    
    for(int i = cnt1 + 1; i <= cnt1 + cnt2; i++){
        if(hhp <= ph[i].a){
            cout << -1;
            return 0;
        }
        hhp = hhp + hp[i].b - hp[i].a;
        res[i] = hp[i].i;
    }
    for(int i = 1; i <= cnt1 + cnt2; i++){
        cout << res[i] << " ";
    }
    return 0;
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题分析

你正在打游戏，需要消灭 n 个敌人，消灭第 i 个敌人的过程会消耗 ai 点的血量，但消灭它之后，你会得到 bi 点的血量回升。初始时，你有 s 点血量。你的目标是求出你能否通过消灭敌人来维持足够的血量。

解决方案

这个问题可以使用动态规划来解决。我们可以维护一个数组 dp[i]，表示在消灭前 i 个敌人后剩余的血量。

int dp[n + 1];
dp[0] = s; // 初始血量

for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] - a[i] + b[i];
    if (dp[i] < 0) {
        dp[i] = -1; // 表示无法通过消灭前 i 个敌人来维持足够的血量
    }
}

答案

最终答案是：通过消灭前 n 个敌人来维持足够的血量的方法是存在的当且仅当 dp[n] >= 0 时。

如果 dp[n] >= 0，说明我们可以通过消灭前 n 个敌人来维持足够的血量。否则，我们无法通过消灭前 n 个敌人来维持足够的血量。