P8847 [JRKSJ R5] 1-1 A 题解
Eleveslaine
·
·
题解
题目传送门
博客食用
题意
将仅有 1,-1 的序列 a 任意重排，使得最大子段和最小。
分析
因为可以任意重排，所以没有必要考虑原来的顺序，故序列 a 可以看作 x 个 1，y 个 -1 构成的可重复集。
考虑怎样让最大子段和最小。可以分两种情况：
- 当 x \le y 时。这种情况比较简单，例如 2 个 1 和 3 个 -1（即 x=2,y=3）。可以这样排列：
\underline{1\;-\!1}\;\underline{1\;-\!1}\;-\!1
这里下划线部分输出了 2 组 1\;-\!1，即输出 x 组 1\;-\!1。
剩下的 (y-x) 个 -1 全部输出到最后即可。
正确性证明：
任意组连续的 1\;-\!1 最大子段和显然为 1（即仅选取一个 1）。而剩下的 (y-x) 个 -1 的最大子段和为 0（即不选），所以整个序列的最大子段和为 1。只要这个序列有一个 1，那么最大子段和一定 >1，达到了最小化最大子段和的目的。
- 当 x>y 时，例如 3 个 1 和 2 个 -1（即 x=3,y=2）。可以这样排列：
\underline{1\;-\!1}\;\underline{1\;-\!1}\;1
下划线部分输出了 2 组 1\;-\!1，即输出 y 组 1\;-\!1。
剩下的 (x-y) 个 1 全部输出到最后即可。
正确性证明：
显然原序列的最大子段和最小值就是 $x-y$，即全选，所以这种方法可以生成最小的最大子段和。（感谢出题人 @[cyffff](https://www.luogu.com.cn/user/365127) 的[帮助](https://www.luogu.com.cn/discuss/530866)）
---
当 $x>y$ 时，一个疑点就是将 $y$ 个 $-1$ 距离平均地放进 $x$ 个 $1$ 中，这也是我的第一种思路。（记作方法二，上面的记作方法一）
例如，当 $x=5,y=3$ 时，两种方法产生的序列如下：
$$\underline{1\;1\;-\!1}\;\underline{1\;1\;-\!1}\;1\;-\!1\quad(\text{Idea }1)$$
$$\underline{1\;-\!1}\;\underline{1\;-\!1}\;\underline{1\;-\!1}\;1\;1\quad(\text{Idea }2)$$
显然它们两个最大子段和分别为 $3,2$（分别选取 $1,1,-1,1,1,-1,1$ 和 $1,1$）。所以按照方法一构造序列的最大子段和最小。
## 程序
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int tmp;
// 1,-1 的个数
int x,y;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) // 统计 x,y
{
scanf("%d",&tmp);
if(tmp==1)
++x;
else
++y;
}
if(x<=y)
{
for(int i=1;i<=x;++i)
{
printf("1 -1 ");
}
for(int i=1;i<=y-x;++i)
{
printf("-1 ");
}
}
else
{
for(int i=1;i<=y;++i)
{
printf("1 -1 ");
}
for(int i=1;i<=x-y;++i)
{
printf("1 ");
}
}
return 0;
}
```