P8847 [JRKSJ R5] 1-1 A 题解

U_star · 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。

仍然将 -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)}。