题目链接

深海潜艇探险

题目描述

一艘潜艇拥有初始能量 ，需要穿越 个危险区域。每个区域 有一个能量消耗 和一个能量补充 。

规则:

  • 潜艇可以自由决定穿越 个区域的顺序。
  • 要穿越区域 ，潜艇当前能量必须严格大于消耗 。
  • 成功穿越后，潜艇的能量变为 当前能量 - c_i + r_i。
  • 任务目标是判断是否存在一个安全的穿越顺序，使得潜艇能成功穿越所有 个区域。

解题思路

这是一个经典的贪心策略问题。我们需要找到一个排序规则，使得潜艇最有可能成功完成任务。

首先，我们可以根据每个区域对潜艇总能量的最终影响，将它们分为两类：

  1. 增益型区域: 穿越后能量会增加或不变，即 。
  2. 损耗型区域: 穿越后能量会减少，即 。

显然，为了积蓄能量以应对更困难的挑战，我们应该优先穿越所有增益型区域，之后再处理损耗型区域。

接下来，我们需要确定每一类区域内部的最优顺序。

1. 增益型区域 () 的内部排序 对于这类区域，每通过一个，我们的总能量就会增加，使得后续任务变得更容易。唯一的风险在于初始消耗 。为了最小化风险，我们应该优先选择那些消耗 最低的区域。这样，我们就能以最小的代价开启能量的“滚雪球”式增长。 因此，增益型区域应按 升序排列。

2. 损耗型区域 () 的内部排序 对于这类区域，每通过一个，我们的总能量就会减少，使得下一次穿越的条件（当前能量 > c_j）变得更加苛刻。为了尽可能保持高的能量水平来应对后续的高消耗，我们应该优先选择那些补充 最高的区域。 为什么呢？假设我们有两个损耗型区域 A 和 B，当前能量为 E。

  • 先走 A: 检查 E > c_A，之后能量变为 E - c_A + r_A。下一步要满足 E - c_A + r_A > c_B。
  • 先走 B: 检查 E > c_B，之后能量变为 E - c_B + r_B。下一步要满足 E - c_B + r_B > c_A。 这两个不等式可以变形为 E > c_A + c_B - r_A 和 E > c_B + c_A - r_B。为了让 E 的要求更宽松，我们需要 c_A + c_B - r 这一项尽可能小，这意味着 r 要尽可能大。所以，优先选择补充量 r 大的区域是更优的策略。 因此，损耗型区域应按 降序排列。

最终算法:

  1. 读取所有区域，将它们分为“增益型”和“损耗型”两个列表。
  2. 对“增益型”列表按 升序排序。
  3. 对“损耗型”列表按 降序排序。
  4. 创建一个最终的遍历顺序：先是排好序的增益型区域，然后是排好序的损耗型区域。
  5. 模拟整个过程：用初始能量 遍历这个最终顺序。在每一步，检查能量是否足够消耗。如果任何一步失败，则不存在安全路径。如果全部成功，则存在。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Zone {
    long long c, r;
};

// 增益型区域排序规则：按消耗 c 升序
bool compareGain(const Zone& a, const Zone& b) {
    return a.c < b.c;
}

// 损耗型区域排序规则：按补充 r 降序
bool compareLoss(const Zone& a, const Zone& b) {
    return a.r > b.r;
}

void solve() {
    int n;
    long long e;
    cin >> n >> e;

    vector<Zone> gain_zones;
    vector<Zone> loss_zones;

    for (int i = 0; i < n; ++i) {
        long long c, r;
        cin >> c >> r;
        if (r >= c) {
            gain_zones.push_back({c, r});
        } else {
            loss_zones.push_back({c, r});
        }
    }

    sort(gain_zones.begin(), gain_zones.end(), compareGain);
    sort(loss_zones.begin(), loss_zones.end(), compareLoss);

    bool possible = true;
    for (const auto& zone : gain_zones) {
        if (e > zone.c) {
            e += (zone.r - zone.c);
        } else {
            possible = false;
            break;
        }
    }

    if (possible) {
        for (const auto& zone : loss_zones) {
            if (e > zone.c) {
                e += (zone.r - zone.c);
            } else {
                possible = false;
                break;
            }
        }
    }

    if (possible) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Zone {
    long c, r;
    public Zone(long c, long r) {
        this.c = c;
        this.r = r;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long e = sc.nextLong();

        List<Zone> gainZones = new ArrayList<>();
        List<Zone> lossZones = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            long c = sc.nextLong();
            long r = sc.nextLong();
            if (r >= c) {
                gainZones.add(new Zone(c, r));
            } else {
                lossZones.add(new Zone(c, r));
            }
        }

        // 增益型区域按消耗 c 升序
        Collections.sort(gainZones, (a, b) -> Long.compare(a.c, b.c));
        // 损耗型区域按补充 r 降序
        Collections.sort(lossZones, (a, b) -> Long.compare(b.r, a.r));

        boolean possible = true;
        for (Zone zone : gainZones) {
            if (e > zone.c) {
                e += (zone.r - zone.c);
            } else {
                possible = false;
                break;
            }
        }

        if (possible) {
            for (Zone zone : lossZones) {
                if (e > zone.c) {
                    e += (zone.r - zone.c);
                } else {
                    possible = false;
                    break;
                }
            }
        }

        if (possible) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


def solve():
    # 读取单组测试数据
    n, e = map(int, input().split())
    zones = []
    for _ in range(n):
        zones.append(list(map(int, input().split())))

    gain_zones = []
    loss_zones = []
    for c, r in zones:
        if r >= c:
            gain_zones.append((c, r))
        else:
            loss_zones.append((c, r))

    # 增益型区域按消耗 c 升序
    gain_zones.sort(key=lambda x: x[0])
    # 损耗型区域按补充 r 降序
    loss_zones.sort(key=lambda x: x[1], reverse=True)
    
    possible = True
    # 优先处理增益区
    for c, r in gain_zones:
        if e > c:
            e += (r - c)
        else:
            possible = False
            break
    
    # 再处理损耗区
    if possible:
        for c, r in loss_zones:
            if e > c:
                e += (r - c)
            else:
                possible = False
                break
    
    if possible:
        print("Yes")
    else:
        print("No")

def main():
    # 读取测试用例数
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心、排序
  • 时间复杂度：，其中 是危险区域的数量。算法的瓶颈在于对两个区域列表的排序。分类和后续的模拟遍历过程都是线性的 。
  • 空间复杂度：，需要额外的空间来存储分类后的两个区域列表。