题目传送门

思路

由于每次操作只能移动一个数到序列末尾，所以第

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：

CPP

#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;
}

CF2104B Move to the End

文章操作

题目传送门

思路

AC Code：

相关推荐

评论

CF2104B Move to the End