AtCoder Beginner Contest 182 解题报告

abc182_d Wandering

AtCoder Beginner Contest 182 的第四题,贪心题。

题目链接:D – Wandering

题意翻译

  • 你有一个机器人和一个长度为 \( n \) 的数列 \( a _ i \);
  • 机器人一开始位于坐标 \( 0 \) 处,然后他会执行下面的指令:
    1. 向正方向移动 \( a _ 1 \) 个单位长度;
    2. 向正方向移动 \( a _ 1 \) 个单位长度,然后再向正方向移动 \( a _ 2 \) 个单位长度;
    3. 向正方向移动 \( a _ 1 \) 个单位长度,然后再向正方向移动 \( a _ 2 \) 个单位长度,然后再向正方向移动 \( a _ 3 \) 个单位长度;
    4. 以此类推;
  • 现在你想要知道,从一开始到结束,机器人距离原点向正方向最大距离是多少?
  • 数据范围:\( 1 \leq n \leq 2 \times 10 ^ 5 \),\( -10 ^ 8 \leq a _ i \leq 10 ^ 8 \)。

题解

显然只要模拟每一步即可,注意的是,每一步更新答案时都要取历史最大值。

时间复杂度为 \( \Theta ( n ) \)。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline ll read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg ll res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10ll * res + (ch ^ '0'), ch = getchar();
    return f ? -res : res;
}

const int MAXN = 2e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

int n;
int a[MAXN];
ll sum[MAXN];

int main(void)
{
    n = read();
    for (reg int i = 1; i <= n; ++i)
    {
        a[i] = read();              //读入 a[i]
        sum[i] = sum[i - 1] + a[i]; //求前缀和
    }
    ll ans = 0, pos = 0, Max = -inf; //三个变量
    for (reg int i = 1; i <= n; ++i)
    {
        Max = max(Max, sum[i]);    //取历史最大值
        ans = max(ans, pos + Max); //更新答案
        pos += sum[i];             //记录位置
    }
    printf("%lld\n", ans); //输出答案
    return 0;
}
Pages: 1 2 3 4 5 6 7 8