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 3

我們只要把999 變成-999就行了，但如果按上面貪心方法，我們要把2，3都改變！

那麼貪心就不可以用了嗎？

有個神奇的東西交叫反悔貪心！

簡單說一下：對於當前不是最優的情況，留到後面重新選擇。

我們肯定要讓每次改變值後，獲得綜合最小的值，但當前的選擇又不一定最有優。

我們可以用一個優先隊列維護，到了每次要改的時候，從優先隊列中選出一個收益最大（使目前累加和最大或最小）的值修改。

註意開$ \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;
}