CF1154D Walking Robot

    • 68通过
    • 131提交
  • 题目来源 CodeForces 1154D
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    Description

    在一个数轴上,有一个机器人要从 $x = 0$ 处移动到 $x = n$ 处。机器人身上有两种电池,第一种是普通电池,第二种是太阳能可充电电池,普通电池的容量上限为 $b$ 点电量,太阳能电池的容量上限为 $a$ 点电量。

    定义数轴上的第 $i$ 段线段代表左端点为 $x = i - 1$,右端点为 $x = i$ 的线段。

    这 $n$ 条线段中,有一些线段可以被太阳照射到。

    当机器人向右移动一个单位时,它会消耗一点电量。

    当机器人走到一个可以被太阳照射到的线段上时,如果他是使用普通电池走到这条线段的并且太阳能电池的电量不满,则可以增加一点电量。这里的线段特指长度为 $1$ 的线段。即如果它从一条被照射到的线段上走到另一条被照射的线段上,依然有可能增加电量。

    机器人总电量为 $0$ 或到达终点时会停下。现在请你求出机器人最远可以走多远。

    Input

    第一行三个整数代表 $n,~b,~a$

    下面一行 $n$ 个整数,第 $i$ 个整数 $s_i$ 描述第 $i$ 条线段是否被阳光照射,如果被照射则为 $1$,否则为 $0$。

    Output

    一行一个整数,代表答案。

    Limitation

    $1~\leq~n,~b,~a~\leq~2~\times~10^5$

    $\forall~i~\in~[1,~n],~0~\leq~s_i~\leq~1$

    Translated By @ 一扶苏一

    题目描述

    There is a robot staying at $ X=0 $ on the $ Ox $ axis. He has to walk to $ X=n $ . You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel.

    The $ i $ -th segment of the path (from $ X=i-1 $ to $ X=i $ ) can be exposed to sunlight or not. The array $ s $ denotes which segments are exposed to sunlight: if segment $ i $ is exposed, then $ s_i = 1 $ , otherwise $ s_i = 0 $ .

    The robot has one battery of capacity $ b $ and one accumulator of capacity $ a $ . For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can't use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can't use the accumulator if its charge is zero).

    If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).

    If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.

    You understand that it is not always possible to walk to $ X=n $ . You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally.

    输入输出格式

    输入格式:

    The first line of the input contains three integers $ n, b, a $ ( $ 1 \le n, b, a \le 2 \cdot 10^5 $ ) — the robot's destination point, the battery capacity and the accumulator capacity, respectively.

    The second line of the input contains $ n $ integers $ s_1, s_2, \dots, s_n $ ( $ 0 \le s_i \le 1 $ ), where $ s_i $ is $ 1 $ if the $ i $ -th segment of distance is exposed to sunlight, and $ 0 $ otherwise.

    输出格式:

    Print one integer — the maximum number of segments the robot can pass if you control him optimally.

    输入输出样例

    输入样例#1: 复制
    5 2 1
    0 1 0 1 0
    
    输出样例#1: 复制
    5
    
    输入样例#2: 复制
    6 2 1
    1 0 0 1 0 1
    
    输出样例#2: 复制
    3
    

    说明

    In the first example the robot can go through the first segment using the accumulator, and charge levels become $ b=2 $ and $ a=0 $ . The second segment can be passed using the battery, and charge levels become $ b=1 $ and $ a=1 $ . The third segment can be passed using the accumulator, and charge levels become $ b=1 $ and $ a=0 $ . The fourth segment can be passed using the battery, and charge levels become $ b=0 $ and $ a=1 $ . And the fifth segment can be passed using the accumulator.

    In the second example the robot can go through the maximum number of segments using battery two times and accumulator one time in any order.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。