U528669 题解

pengyirui · 2025-01-23 16:37:53 · 个人记录

这是一篇贪心题解，因为它比DP好思考（~我不会告诉你我不知道可以使用DP~）

思路

题目大意

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

样例分析

样例1

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

样例2

请看下图（请原谅我丑陋无比的图）。

样例3

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

样例4

分析

文字描述

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

流程图

代码

#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;
}