专栏文章

U528669 题解

个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqexaeb
此快照首次捕获于
2025/12/04 03:41
3 个月前
此快照最后确认于
2025/12/04 03:41
3 个月前
查看原文
这是一篇贪心题解,因为它比DP好思考(~我不会告诉你我不知道可以使用DP~)

思路

题目大意

题目的意思是有两只青蛙从一岸跳到另一岸,每只青蛙初始可以跳m米,助跳器可以让青蛙的跳跃距离变成k米,要问至少传递多少次助跳器。
题目给出了一个限制,就是当两只青蛙距离大于q时无法传递。

样例分析

样例1

额……
此样例是用来展示特殊情况的,无需分析。

样例2

请看下图(请原谅我丑陋无比的图)。

样例3

与样例2基本一样,不再赘述。

样例4

分析

文字描述

本题可以考虑先让A向前,直到再跑一次就无法传递了让B跑,B需要就传给他,不用就B跑了之后A跑,直到到达终点。

流程图

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a_can,zhu_can,juli=0,kcdjl,a[999999],b[999999],a_de_wei_zhi,b_de_wei_zhi,zou=1,zhu=1,ans;//1代表a,2代表b 
bool zero1=true,zero2=true,ar1=false,ar2=false;
signed main()
{
	//freopen("d.in","r",stdin);
	//freopen("d.out","w",stdout);
	cin>>n>>a_can>>zhu_can>>kcdjl;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	if(i!=1)if(a[i]-a[i-1]>a_can)zero1=false;
	}
	for(int i=1;i<=n;i++)
    {
    	cin>>b[i];
    	if(i!=1)if(b[i]-b[i-1]>a_can)zero2=false;
	}
	if(zero1&&zero2)
	{
		cout<<0;
		return 0;
	}
	if(zero1&&(zero2==false))
	{
		cout<<1;
		return 0;
	}
	if(zero1==false&&zero2==true)
	{
		cout<<0;
		return 0;
	}
	while(!ar1||!ar2)
	{
		if(zou==1)
		{
			if(zhu==1)
			{
				a1:
			    while(ar2||(a[a_de_wei_zhi+1]-b[b_de_wei_zhi])<=kcdjl)
			    {
			    	a_de_wei_zhi++;
			    	if(a_de_wei_zhi==n)
			    	{
			    		ar1=true;
			    		break;
			    	}
		    	}
			}
			else
			{
				if(ar2||(a[a_de_wei_zhi+1]-b[b_de_wei_zhi])<=kcdjl)
			    {
			    	if(a[a_de_wei_zhi+1]-a[a_de_wei_zhi]>a_can&&zhu==2)
					{
						zhu=1,ans++;
						goto a1;
					}
			    	a_de_wei_zhi++;
			    	if(a_de_wei_zhi==n)
			    	{
			    		ar1=true;
			    		break;
			    	}
		    	}
			}
			if(!ar2)zou=2;
		}
		else
		{
			if(zhu==2)
			{
				a2:
			    while(ar1||(b[b_de_wei_zhi+1]-a[a_de_wei_zhi])<=kcdjl)
			    {
			    	b_de_wei_zhi++;
			    	if(b_de_wei_zhi==n)
			    	{
			    		ar2=true;
			    		break;
			    	}
		    	}
			}
			else
			{
				if(ar1||(b[b_de_wei_zhi+1]-a[a_de_wei_zhi])<=kcdjl)
			    {
			    	if(b[b_de_wei_zhi+1]-b[b_de_wei_zhi]>a_can&&zhu==1)
					{
						zhu=2,ans++;
						goto a2;
					}
			    	b_de_wei_zhi++;
			    	if(b_de_wei_zhi==n)
			    	{
			    		ar2=true;
			    		break;
			    	}
		    	}
			}
			if(!ar1)zou=1;
		}
	}
	cout<<ans;
	return 0;
}

评论

1 条评论,欢迎与作者交流。

正在加载评论...