自动搬运

查看原文

来自洛谷，原作者为

	U_star 手提玉剑斥千军，昔日锦鲤化金龙！

搬运于2025-08-24 22:43:03，当前版本为作者最后更新于2022-12-04 12:09:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8847 [JRKSJ R5] 1-1 A

普通思路：枚举所有可能，然后每次求出最大子段和。可通过 $\operatorname{40pts}$ 的数据。

如果想要AC，时间复杂度就需要控制在 $\operatorname{O(nlogn)}$ 之内。

注意此题有一个特殊性质：$a_i$ 只能为 $1$ 或 $-1$。也就是说，给出的序列中只有 $1$ 或 $-1$。

根据本题的特殊性，我们可以分类讨论以下三种情况：

1. $-1$ 的数量大于 $1$ 的数量

这时我们就可以把 $-1$ 和 $1$ 配对放在一起，大概就是像下面这样：

然后将多余的 $-1$ 放在序列的末尾。考虑这种排列的最大子段和：

• 根据贪心策略，最后多余的 $-1$ 一定不会选。
• 只选择一个数时，选择一个 $1$ 为最优。
• 选择多个数时，由于 $-1$ 和 $1$ 相邻，所以相邻的两数会互相抵消，导致最后不会剩下数或者只会剩下一个数，其实相当于是选择一个数的情况。

所以这种方法最大子段和为 $1$。

可以证明，只要数列中有 $1$，无论如何重排，最大子段和都至少为 $1$，因为可以只选择一个 $1$。因此，这种排列是最优解。

2. $-1$ 的数量等于 $1$ 的数量

这种情况类似于上面的情况，也是将 $-1$ 和 $1$ 配对，最大子段和也为 $1$。

3. $-1$ 的数量小于 $1$ 的数量

仍然将 $-1$ 和 $1$ 配对（注意！一定要把 $-1$ 放在后面），然后将多余的 $1$ 放在序列的末尾。

这种排列的最大子段和为 $x$（$x$ 为 $1$ 的数量减去 $-1$ 的数量），因为后面多余的 $1$ 一定要选，而前面的无论如何选择都一定会互相抵消。

证明：由于可以选择整个序列，所以无论怎么重排，最大子段和必然不小于 $x$。因此，这种排列是最优解。

至于为什么要把 $-1$ 放在后面？因为最后面的全都是 $1$，也就是说把 $1$ 放后面会使最大子段和增加 $1$。

AC Code：

#include<bits/stdc++.h> 
using namespace std;
int a,v1,v2;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(a==1)
		v1++;
		else
		v2++;
	}
	if(v2==v1)
	{
		for(int i=1;i<=n;i++)
		{
			if(i%2)
			cout<<1<<" ";
			else
			cout<<-1<<" ";
		}
	}
	else if(v2>v1)
	{
		for(int i=1;i<=v1*2;i++)
		{
			if(i%2)
			cout<<1<<" ";
			else
			cout<<-1<<" ";
		}
		for(int i=1;i<=n-v1*2;i++)
		cout<<-1<<" ";
	}
	else
	{
		for(int i=1;i<=v2*2;i++)
		{
			if(i%2)
			cout<<1<<" ";
			else
			cout<<-1<<" ";
		}
		for(int i=1;i<=n-v2*2;i++)
		cout<<1<<" ";
	}
	return 0;
}

时间复杂度：$\operatorname{O(n)}$。