解题思路

这是一道典型的最短路径问题，可通过广度优先搜索（BFS）或动态规划（DP）解决。由于每个建筑物只能向右荡摆，且荡摆的水平距离受当前建筑物高度限制，我们可以将问题转化为在图中寻找从起点到终点的最短路径，其中节点为建筑物，边表示可行的荡摆操作。

方法选择：

动态规划（推荐）： 定义dp[i]为到达第 $i$ 个建筑物所需的最少荡摆次数。对于每个建筑物 $i$，遍历所有$j < i，$若$Xi - Xj ≤ Yj$（即从 j 荡摆到 i 的水平距离不超过 j 的高度），则更新$dp[i] = min(dp[i], dp[j] + 1)$。 BFS： 将每个建筑物视为图中的节点，从起点出发，每次将所有可达的建筑物加入队列，记录步数。适用于节点数较大的情况，但需注意优化以避免超时。 关键点： 荡摆合法性：从建筑物 j 荡摆到 i 的条件为$Xi - Xj ≤ Yj，且 i > j$$（保证向右荡摆）。 初始条件：dp[0] = 0（起点无需荡摆），其余dp[i]初始化为无穷大。 结果判断：若dp[N-1]仍为无穷大，说明无法到达，输出 - 1；否则输出dp[N-1]。

cpp

#include #include #include using namespace std;

int main() { int K; cin >> K; while (K--) { int N; cin >> N; vector<pair<int, int>> buildings(N); for (int i = 0; i < N; ++i) { cin >> buildings[i].first >> buildings[i].second; }

    vector<int> dp(N, INT_MAX);
    dp[0] = 0; // 起点无需摆动
    
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (buildings[i].first - buildings[j].first <= buildings[j].second) {
                if (dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    
    if (dp[N-1] == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << dp[N-1] << endl;
    }
}
return 0;

}