10、灵能传输

题目 灵能传输

思路分析

题目意思又表达不清楚 到底可以传输几次 求的是什么东西 绝对值的最大值 恶心

跳过跳过

代码实现

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

int t, n;

LL s[N], a[N]; // s为前缀和数组 a为存放前缀和顺序的数组

bool st[N];

int main()

{

    cin >> t;

    while (t--)

    {

        cin >> n;

        memset(st, 0, sizeof st);

        for (int i = 1; i <= n; i++)

            cin >> s[i], s[i] += s[i - 1];

        LL s0 = s[0], sn = s[n];

        if (s0 > sn)

            swap(s0, sn);

        sort(s, s + n + 1);

        // 寻找排完序后s0和sn的位置

        // 如果s0和sn相同的话则前面的为s0 后面的为sn

        for (int i = 0; i <= n; i++)

            if (s[i] == s0)

            {

                s0 = i;

                break;

            }

        for (int i = n; i >= 0; i--)

            if (s[i] == sn)

            {

                sn = i;

                break;

            }

        int l = 0, r = n;

        for (int i = s0; i >= 0; i -= 2)

        {

            a[l++] = s[i];

            st[i] = 1;

        }

        for (int i = sn; i <= n; i += 2)

        {

            a[r--] = s[i];

            st[i] = 1;

        }

        for (int i = 0; i <= n; i++)

            if (!st[i])

                a[l++] = s[i];

        LL res = 0;

        for (int i = 1; i <= n; i++)

            res = max(res, abs(a[i] - a[i - 1]));

        cout << res << endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 第十四届 c++ B组 省赛 🏠 00-刷题理模型 ➡️ 1、组队