[数据结构与算法]I. Distance

I. Distance

[link](Problem - I - Codeforces)

题意

给你一个坐标轴，给你n个点，然后给你n - 1个距离表示从从前到后相邻两点的距离，之后让你输出，n个数，表示选出i个点之后任意两个点之间的距离和，要求每一个输出都是最大的。

题解

转换一下相当于从当前局面插进一个新的点，新的局面的权值就是上一个局面的权值，加上当前这个点和前面所有点构成的贡献。因为要两点距离尽可能大，我们尽可能的从两边往中间开始插点。每次如果是奇数点就往左边插点，偶数就往右边插点，每一个偶数的点都会和上次的奇数的点构成一个新的区间（用一个前缀和维护即可）产生贡献，奇数的点就相当于和前面的区间产生贡献，用一个变量存前面的产生的区间，然后动态维护一下就行。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
LL a[N], res[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 2; i <= n; i ++ ) {
            cin >> a[i];
            a[i] += a[i - 1];
        }
        LL t = a[n];
        int l = 0;
        for (int i = 2; i <= n; i ++ ) {
            if (i & 1)  {
                l ++;
                res[i] = res[i - 1]  + t;
                t += a[n - l] - a[l + 1];
            }
            else res[i] = res[i - 1] + t;
        }
        cout << res[1];
        for (int i = 2; i <= n; i ++ )  
            cout << " " << res[i];
        cout << endl;
    }
    return 0;
}