题解：贝西的地标访问之旅（Landmark Tour）

题目描述

贝西从数轴原点（$x=0$）出发，希望在日落前（$T$分钟内）访问尽可能多的地标。地标按离原点由近到远的顺序访问（距离相同的情况不存在）。每移动1单位距离需要1分钟，求最多能访问的地标数量。

算法思路

问题的核心是贪心策略：每次选择当前未访问的离原点最近的地标，确保在有限时间内访问最多地标。具体步骤如下：

1. 排序地标：将所有地标按离原点的距离（绝对值）从小到大排序，模拟贝西的访问顺序。
2. 模拟访问过程：从原点出发，依次累加访问每个地标的移动时间，若总时间超过$T$则停止，否则继续。

复杂度分析

• 时间复杂度：

  • 排序操作：$O(N \log N)$，使用快速排序实现。
  • 遍历地标：$O(N)$，每个地标仅访问一次。
    总时间复杂度为 $O(N \log N)$，适用于题目中$N \leq 50,000$的限制。

• 空间复杂度：
  仅需存储地标位置的数组，空间复杂度为 $O(N)$。

标程

以下是修正后的C++代码，正确处理了时间累加和边界条件：

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

// 比较函数：按绝对值从小到大排序
bool cmp(const int a, const int b) {
    return abs(a) < abs(b);
}

int main() {
    int num[50005];  // 存储地标位置
    int n, t;
    scanf("%d%d", &t, &n);  // 输入时间T和地标数量N
    
    // 读取地标位置
    for (int i = 0; i < n; ++i)
        scanf("%d", &num[i]);
    
    // 按绝对值从小到大排序（访问顺序）
    sort(num, num + n, cmp);
    
    int ans = 0;  // 记录已访问的地标数
    long long sum = 0;  // 累计时间（避免int溢出）
    int current_pos = 0;  // 当前位置，初始为原点
    
    // 遍历排序后的地标，模拟访问过程
    for (int i = 0; i < n; ++i) {
        int next_pos = num[i];  // 下一个地标的位置
        long long move = abs(next_pos - current_pos);  // 本次移动的距离
        
        // 若加上本次移动时间超过T，停止访问
        if (sum + move > t)
            break;
        
        // 未超时，更新状态
        sum += move;  // 累加时间
        ans++;  // 成功访问一个地标
        current_pos = next_pos;  // 更新当前位置
    }
    
    printf("%d\n", ans);  // 输出最大访问数
    return 0;
}