CF链接：Least Prefix Sum

Luogu链接：Least Prefix Sum

$ {\scr \color {CornflowerBlue}{\text{Solution}}} $

先来解释一下题意：

给定一个数组，问最少把多少个数变成相反数，使得$ \forall \cal{i}$,$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$

发现对于所有数据点，$ \cal{n} \le 2 \times 10^5$，说明需要 $ Ο(\cal{n \log n}) $ 或者 $ O(\cal{n}) $的算法。

分析一下题目，发现要分成$ \cal{i} > \cal{m}$ 与$ \cal{i} < \cal{m}$两种情况分类讨论

当 $\cal{i}$ $ > \cal{m}$时：

什么时候才能使$ \sum_{k=1}^i a_k$ $ \le$ $ \sum_{k=1}^m a_k$ 成立呢？

是不是只要使新加的每一段都小于等于0就行了？（$ \sum_{k=m}^i a_k$ $ \le$ $ 0$）

也很好证明：一个数（$ \sum_{k=1}^m a_k$）加上一个小于等于0的数（$ \sum_{k={m+1}}^i a_k$），一定不大于原数。

当 $\cal{i}$ $ < \cal{m}$时：

同理，只要使后加的每一段都小于等于0就行了（$ \sum_{k=i}^i a_k$ $ \ge$ $ 0$）

也很好证明：一个数（$ \sum_{k=1}^i a_k$）加上一个大于等于0的数（$ \sum_{k=i}^m a_k$），一定不小于原数。

而且，由于这两种情况类似（博主太懒），那就只考虑当 $\cal{i}$ $ > \cal{m}$的情况吧。

问题已经转化完了，接下来怎么办？

第一眼想到的是贪心。

设当前要取第$\cal{i}$个。

有一个不成熟的贪心：如果目前累加和加上$a_i$还是小于等于$0$的，就加上$a_i$，如果大于$0$了，就把$a_i$取反，$ ans+1$。

Hack数据

5 1

1 -1000 999 2 100

我们只要把999 变成-999就行了，但如果按上面贪心方法，我们要把2，100都改变！

那么贪心就不可以用了吗？

有个神奇的东西交叫反悔贪心！

简单说一下：对于当前不是最优的情况，留到后面重新选择。

我们肯定要让每次改变值后，获得综合最小的值，但当前的选择又不一定最有优。

我们可以用一个优先队列维护，到了每次要改的时候，从优先队列中选出一个收益最大（使目前累加和最大或最小）的值修改。

注意开$ \cal{long long}$并且清空优先队列！

Code（赛时代码，过丑见谅QwQ）:

#include<bits/stdc++.h>

#define L long long

using namespace std;

L a[200005];

priority_queue<L,vector<L>,greater<L> > q;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        while(!q.empty()) q.pop();

        int n,m,ans=0;

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

        if(n==1)

        {

            printf("0\n");

            continue;

        }

        if(m==1)

        {

            L mu=0;

            for(int i=m+1;i<=n;i++)

            {

                if(a[i]>=0) mu+=a[i];

                else if(a[i]<0 && mu+a[i]>=0)

                {

                    q.push(a[i]);

                    mu+=a[i];

                }

                else

                {

                    ans++;

                    q.push(a[i]);

                    mu+=a[i];

                    mu-=2*q.top();

                    q.pop();

                }

            }

            printf("%d\n",ans);

            continue;

        }

        L mu=0;

        for(int i=m+1;i<=n;i++)

        {

            if(a[i]>=0) mu+=a[i];

            else if(a[i]<0 && mu+a[i]>=0)

            {

                q.push(a[i]);

                mu+=a[i];

            }

            else

            {

                ans++;

                q.push(a[i]);

                mu+=a[i];

                mu-=2*q.top();

                q.pop();

            }

        }

        while(!q.empty()) q.pop();

        mu=0;

        for(int i=m;i>=2;i--)

        {

            if(a[i]<=0) mu+=a[i];

            else if(a[i]>0 && mu+a[i]<=0)

            {

                q.push(-a[i]);

                mu+=a[i];

            }

            else

            {

                ans++;

                q.push(-a[i]);

                mu+=a[i];

                mu+=2*q.top();

                q.pop();

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

CF1779C Least Prefix Sum 题解

CF链接：Least Prefix Sum

Luogu链接：Least Prefix Sum

$ {\scr \color {CornflowerBlue}{\text{Solution}}} $

先来解释一下题意：

最新文章

热门文章