OJ P1809 wzy的跑步

 这题我没有采用什么复杂的算法，简单的分类讨论之后一次过~

首先分三种情况：（但是这三种情况并不是完全的真正独立）

一是第一点有水塘；

二是最后一个点有水塘；

三是首尾都没有水塘。

这里说明一下为什么我要单独讨论首尾，因为wzy必须从1出发，到n结束，也就是说即使位置1和位置n有水塘，wzy也必须要踩

整体思路如下：

如果位置1（第一个点）有水塘，找到第一个无水塘的地方right，如果位置n（最后一个点）有水塘，找到最后一个无水塘的地方left，令begin=right，end=left（可以画个图理解一下）。此时整条路被分成了三段，中间两个断点分别是right（begin）和left（end)

易得：从位置i1到i2（i1，i2干燥，之间全是水塘）需要踩水塘的次数为：

（i2-i1-1）/k

对于第一段道路，若已知第一点有水塘，则wzy先到第一个点，此时踩了一次水塘，然后将位置1作为出发点，假设位置1无水塘（因为已经记录过踩水塘次数+1），找到第一个实际干燥的地方right，所需要经历的踩水塘次数为count+=（right-1-1）/k+1，这里的第一个1则表示假设干燥的位置1，最后的+1则表示踩了第一个水塘。第三段尾部同理，count+=（n-left-1）/k+1。

接下来是中间道路，赋予了新的begin和end（在上文），这两个点都是干燥的，因为begin和end的初始值分别为1和n，所以即使位置1和位置n也是干燥的，也能轻松合并情况。找到第一个干燥点后，下标赋值为left，往后遍历，找到第二个干燥点，下标赋值为right，利用公式，count+=（right-left-1）/k；然后将right赋值给left，再找left的下一个right，以此类推......

其实思路很简单，可能被我讲复杂了

完整AC代码如下：

#include
using namespace std;int flag[10005];            	//堆空间，默认初始化全是0，等价于 int flag[10005]={0}; //flag值为0表示没水塘，为1表示有水塘
int main(){int n,m,k;               	//n，m，k分别代表路径的长度，积水的个数以及wzy一次最远可以跨多远int num; cin>>n>>m>>k;for(int i=1;i<=m;i++){ 		//将有水塘的点赋值为1 cin>>num;flag[num]=1;            }int left=0,right=1,count=0; //count为需要踩水塘的次数 int begin=1,end=n;          //重新定义begin，end变量，方便分类讨论 //若第一点有水塘 if(flag[1]==1){for(int i=2;i<=n;i++){	//找到第二个是水塘的点 if(flag[i]==0){right=i;break;}} count+=(right-1-1)/k+1;begin=right;}//如果最后一个点有水塘if(flag[n]==1){for(int i=n-1;i>=1;i--){//找到倒数第二个是水塘的点 if(flag[i]==0){left=i;break;}}count+=(n-left-1)/k+1;end=left;} //此时起点和终点都没有水塘 if(begin!=end){for(int i=begin;i<=end;i++){if(flag[i]==0){  left=i;int j;for(j=i+1;j<=end;j++){if(flag[j]==0){right=j;break;}}if(j>end) break;   //不写这句会陷入死循环！ count+=(right-left-1)/k;}i=right-1;}}//输出结果 cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！