题解

题面描述

多多在一维数轴上玩一个“传送门”游戏：

• 初始位置在 $x = 0$。
• 有 $n$ 个传送门，每个传送门有一个“传送值” $a_i$，可将当前位置 $t$ 传送至 $t + a_i$。
• 每个传送门只能使用一次，可以按任意顺序使用这些传送门。
• 多多还拥有一个**“反转”技能**，可将位置从 $x = t$ 立刻变为 $x = -t$。该技能最多使用一次，也可以选择不使用。

在多多使用完全部 $n$ 个传送门后，我们希望知道：
多多与初始位置 $x = 0$ 的最远距离可以是多少？

2. 思路

核心思路可以归纳为一句话：

最终能够达到的最大距离，其实就是所有传送值绝对值的总和。

下面给出简要推导/解释：

1. 若不使用反转技能，最终位置为所有传送值的和 $S = \sum a_i$，距离为 $|S|$。
2. 若使用反转技能，可以选择在传送的过程中某个时刻“翻转”坐标，使得之前可能累积的“负方向”或“正方向”位移被翻转，后续再叠加剩余传送值，从而可能把所有数的“正负贡献”都变成正方向(或负方向)来最大化与 0 的距离。
3. 事实上，只要我们先把所有可能为负的传送值先累加（让位置走到一个可能比较大的负数），然后使用一次反转技能，就将这个负数坐标翻到正的，再把所有正传送值加上去，就可以得到绝对值意义上的最大累积。
4. 数学上可以验证，这样的做法最终能让我们“把所有 $|a_i|$”都加到同一方向上，而这恰好就是所有 $|a_i|$ 的总和。

因此，无论 $a_i$ 是正是负，都可以在合适的时机（或顺序）使用一次翻转技能，使得最终的结果是：

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    long long ans = 0; // 用long long防止溢出

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        ans += llabs(x); // 累加绝对值
    }

    cout << ans << "\n"; // 输出最终结果
    return 0;
}

python

n = int(input().strip())              # 第一次输入，用来读取 n
numbers = list(map(int, input().split()))  # 第二次输入，一次读取所有 n 个整数

ans = sum(abs(x) for x in numbers)    # 对每个数字取绝对值后累加
print(ans)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long ans = 0; // 用long来累加绝对值

        for(int i = 0; i < n; i++){
            long x = sc.nextLong();
            ans += Math.abs(x);
        }

        System.out.println(ans);
    }
}

题目内容

多多在玩一个传送门游戏。

游戏开始时多多在一维数轴的$x=0$处。他有$n$个传送门，每个传送门都有一个传送值$a_i$，他能

使用该传送门从$x=t$位置传送到$x=t+a_i$，传送门是消耗品，只能使用一次。同时他还有一 个“反转”技能，使用该技能可以立即从位置$x=t$“反转”到$x=-t$.

多多可以以任意顺序使用这些传送门，可以在任何时候使用“反转”技能(最多用一次，也可以不 用)，问用完所有传送门后，多多到初始位置$x=0$最远的距离为多少?

输入描述

第一行为一个正整数$n(1≤n≤10^5)$，

第二行为$n$个整数 $a_1,a_2,….,a_n (-10^4≤a_i≤10^4)$。

输出描述

输出用完所有传送门后，多多到初始位置距离的最大值。

补充说明

对于 $60$ 的数据,$1≤n≤10$;

对于100% 的数据，$1≤n≤10^5,-10^4≤a_i≤10^4$.

样例1

输入

4
1 -2 3 -4

输出

0 1 2 4 4 

说明

最初多多在位置$x=0$处;

他先选择使用第$2,4$个传送门，到达位置$x=0+a_2+a_4=0-2-4=-6$;

然后他使用技能“反转”，到达位置$x=6$;

最后选择第$1,3$个传送门，到达位置$x=6+a_1+a_3=6+1+3=10$，与初始位置距离最大为$10$。