跳板问题（贪心算法+细节思考）

首先直接看题：

 这题直接贪心其实问题不大：

下面先展示我的一个错误代码：

# include<iostream>
# include<vector>
# include<algorithm>using namespace std;int main()
{int N,M;cin>>N>>M;vector<vector<int>> arr(N,vector<int>(2));for(int i=0;i<N;i++){cin>>arr[i][0]>>arr[i][1];}// 感觉贪心应该就能解决int distance = 0;int step = 0;int i = 0;// 可能少考虑了一点while(distance<=M){if(distance<=arr[i][0]){step+=arr[i][0]-distance;distance = arr[i][0]+arr[i][1];}else if(distance>arr[i][0]){i++;if(i>=N){step+=M-distance;break;}}}cout<<step<<endl;return 0;
}

其实整体思路是没有问题的，

但题目里面有一个细节，就是说“每个跳板能够将胡同学发射到一定距离内的任意位置。“

这时候问题就来了，比如距离起点为5，能跳长度为6的这样一个板，它在5-11之间还是会有其他的跳板，所以，在5-11他也不需要自行走路，因为他目前的跳板可以把他送到5-11范围内的任意位置，那么如果有这样一个跳板，距离起点7，跳板长度是10，那么借助这个跳板就可以直接达到17这个位置，这是之前代码没有考虑到的，之前的代码直接是认为做上5跳板，到达的位置就是11，这就是问题所在，所以i++的过程中需要进行一个判断。

所以最终代码就是：

# include<iostream>
# include<vector>
# include<algorithm>using namespace std;int main()
{int N,M;cin>>N>>M;vector<vector<int>> arr(N,vector<int>(2));for(int i=0;i<N;i++){cin>>arr[i][0]>>arr[i][1];}// 感觉贪心应该就能解决int distance = 0;int step = 0;int i = 0;// 可能少考虑了一点int current_pos = 0;while(distance<M&&i<N){if(current_pos<=arr[i][0]){step+=arr[i][0]-distance;current_pos = arr[i][0];}distance = arr[i][0]+arr[i][1]; // 前一个跳板能达到的最远距离if(distance>current_pos){current_pos = distance;}i++;}if(current_pos<M){step+=M-current_pos;}cout<<step<<endl;return 0;
}

最主要的点就是一个比较。