题解：P6821 [PA2012] Tanie linie

· · 题解

P6821 反悔贪心经典例题

写完弱化版双倍经验 P10478 过来被硬控，研究好一会才过，写篇题解祭一下。

Solution

题意不难理解。

首先可以发现，如果没有 k 这个限制（或者说 k 足够大），那么我们的答案就是序列中所有正数的和。

那么我们可以先求出这样情况下的正区间个数 cnt，然后再把这个 cnt 逐步降到 k。

怎么降？有两种方式：

那么可以发现，要求这些被抛弃掉的贡献，实质就是求从若干个正负区间中选择互不相邻的 (cnt-k) 个区间，使这些区间的绝对值之和最小。

把区间视作点，那么这道题就被完美转化成了 P1484，即反悔贪心的模板。

笔者采用优先队列 + 链表来实现。

这里有一个实现上的小问题。

在把初始的 a 序列划分成若干个正负区间的时候，如果这么写（已经开了 long long）：

for(int i = 1;i <= n;i++)
{
    a[i] = read();
    if(a[i] * b[tot] < 0)b[++tot] = a[i];
    else b[tot] += a[i];
}

逻辑上没有问题，但是会 WA #6，因为可能会爆 long long。（自己算算，差不多能大到十的二十几次）

所以就别用乘法：

for(int i = 1;i <= n;i++)
{
    a[i] = read();
    if(a[i]<0&&b[tot]>0 || a[i]>0&&b[tot]<0)b[++tot] = a[i];
    else b[tot] += a[i];
}

这样就行啦。

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;

int read()
{
    int ret = 0,k = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')k = -1;
    for(;c >= '0' && c <= '9';c = getchar())ret = ret*10+c-48;
    return ret*k;
}

int n,m,ans;
int a[N],b[N],tot = 1,cnt;
int l[N],r[N];
bool flag[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

signed main()
{
    n = read(),m = read();
    for(int i = 1;i <= n;i++)
    {
        a[i] = read();
        if(a[i]<0&&b[tot]>0 || a[i]>0&&b[tot]<0)b[++tot] = a[i];
        else b[tot] += a[i];
    }
    for(int i = 1;i <= tot;i++)
    {
        if(b[i] > 0)cnt++,ans += b[i];
        q.push(make_pair(abs(b[i]),i));
        l[i] = i-1,r[i] = i+1;
    }
    l[0] = 0,r[0] = 1,l[tot+1] = tot,r[tot+1] = tot+1;
    while(cnt > m)
    {
        while(flag[q.top().second])q.pop();
        int u = q.top().second;q.pop();
        if(b[u] < 0 && (l[u] == 0 || r[u] == tot+1))continue;
        ans -= abs(b[u]),cnt--;
        b[u] += b[l[u]] + b[r[u]];
        flag[l[u]] = flag[r[u]] = 1;
        l[u] = l[l[u]],r[u] = r[r[u]];
        r[l[u]] = u,l[r[u]] = u;
        q.push(make_pair(abs(b[u]),u));
    }
    printf("%lld",ans);
    return 0;
}