幻兽防御战

题目分析

小红守护遗迹，有 $n$ 只幻兽正在靠近，第 $i$ 只幻兽初始距离为 $d_i$ ，速度为 $v_i$ ，到达时间为 $t_i = d_i / v_i$ 。小红的弩每分钟只能发射一次：在第 $k$ 分钟开始时（ $k = 0, 1, 2, \ldots$ ），她可以消灭一只尚未到达的幻兽。若此时存在某只存活的幻兽满足 $t_i \le k$ ，则遗迹在射击前就被摧毁。求最多能消灭多少只幻兽。

思路

贪心（最早截止时间优先）

这是一个经典的调度问题：每分钟只能处理一个任务，每个任务有一个截止时间（幻兽到达时间），要在截止前完成尽可能多的任务。

关键观察：如果按到达时间从小到大排序，在第 $k$ 分钟优先消灭到达时间最早的幻兽，一定不会比其他策略更差。这就是贪心策略——最早截止时间优先（Earliest Deadline First）。

算法步骤：

计算每只幻兽的到达时间 $t_i = d_i / v_i$ 。
按 $t_i$ 从小到大排序。
依次遍历：在第 $k$ 分钟，检查当前幻兽是否满足 $t_i > k$ （即还没到达）。若是，消灭它， $k$ 加 $1$ ；否则遗迹已被摧毁，停止。

避免浮点精度问题：比较 $d_i / v_i$ 与 $k$ 等价于比较 $d_i$ 与 $k \cdot v_i$ （因为 $v_i > 0$ ），排序时用交叉相乘 $d_a \cdot v_b$ 与 $d_b \cdot v_a$ 比较。

贪心正确性：假设存在一个最优方案，在某一分钟选择了到达时间更晚的幻兽而非更早的，交换两者的射击顺序不会导致失败（更早的幻兽被推迟消灭，但它的截止时间更早，原方案能在更晚时刻消灭它，说明在更早时刻也一定不会超时），因此按最早截止时间排序是最优的。

示例推演

输入 d = [1, 4, 4]，v = [5, 2, 3]，到达时间为 $[0.2, 2.0, 1.33]$ 。

排序后顺序：幻兽 1（ $t=0.2$ ）、幻兽 3（ $t\approx1.33$ ）、幻兽 2（ $t=2.0$ ）。

分钟 $k$	待消灭幻兽	到达时间	$t_i > k$ ？	操作
0	幻兽 1	0.2	$0.2 > 0$ ✓	消灭
1	幻兽 3	1.33	$1.33 > 1$ ✓	消灭
2	幻兽 2	2.0	$2.0 > 2$ ✗	遗迹被摧毁

答案为 $2$ 。

代码

C++
Java
Python3
JavaScript

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> d(n), v(n);
    for(int i = 0; i < n; i++) cin >> d[i];
    for(int i = 0; i < n; i++) cin >> v[i];

    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return d[a] * v[b] < d[b] * v[a];
    });

    int ans = 0;
    for(int k = 0; k < n; k++){
        int i = idx[k];
        if(d[i] <= (long long)k * v[i]) break;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] d = new long[n], v = new long[n];
        for (int i = 0; i < n; i++) d[i] = sc.nextLong();
        for (int i = 0; i < n; i++) v[i] = sc.nextLong();

        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Long.compare(d[a] * v[b], d[b] * v[a]));

        int ans = 0;
        for (int k = 0; k < n; k++) {
            int i = idx[k];
            if (d[i] <= (long) k * v[i]) break;
            ans++;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
d = list(map(int, input().split()))
v = list(map(int, input().split()))

idx = sorted(range(n), key=lambda i: d[i] / v[i])

ans = 0
for k in range(n):
    i = idx[k]
    if d[i] <= k * v[i]:
        break
    ans += 1

print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const d = lines[1].split(' ').map(Number);
    const v = lines[2].split(' ').map(Number);

    const idx = Array.from({length: n}, (_, i) => i);
    idx.sort((a, b) => d[a] * v[b] - d[b] * v[a]);

    let ans = 0;
    for (let k = 0; k < n; k++) {
        const i = idx[k];
        if (d[i] <= k * v[i]) break;
        ans++;
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(n \log n)$ ，排序的开销。
空间复杂度： $O(n)$ ，存储下标数组。