CF2104B Move to the End

Andy1101 · 2025-05-25 11:22:59 · 题解

题目传送门

思路

由于每次操作只能移动一个数到序列末尾，所以第 i 次询问中 a_{n-i+2} \sim a_n 的所有数是一定在答案中的，此时我们只需要再求出 a_1 \sim a_{n-i+1} 中的最大值即可，可以维护前缀最大值和前缀和来进行询问。我们规定 maxx_i 是 a_1 \sim a_i 中所有数的最大值，sum_i 是 a_1 \sim a_i 中所有数的总和。那么第 i 次询问的答案就是 sum_n-sum_{n-i+1}+maxx_{n-i+1}。

这时的代码总时间复杂度为 O(tn)。

注：sum 数组要开 long long。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
long long sum[N];
int maxx[N];
void solve()
{
    int n;
    cin >>n;
    for(int i=1;i<=n;i++)
    {
        cin >>a[i];
        sum[i]=sum[i-1]+a[i];
        maxx[i]=max(maxx[i-1],a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        cout <<(sum[n]-sum[n-i+2-1])+maxx[n-i+1]<<" ";
    }
    cout <<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}