00:00/00:00

题意:

N个整数组成的序列a[1],a[2],a[3],…,a[n],将这N个数划分为互不相交的M个子段,并且这M个子段的和是最大的。如果M \geqslant N个数中正数的个数,那么输出所有正数的和。
例如:-2 11 -4 13 -5 6 -2,分为2段,11 -4 13一段,6一段,和为26。

Input:

1行:2个数NM,中间用空格分隔。N为整数的个数,M为划分为多少段。(2 \leqslant N , M \leqslant 5000)
2 – N+1行:N个整数 (-10^9 \leqslant a[i] \leqslant 10^9)

Output:

输出这个最大和

分析:

这道题明显要么O(n),要么O(n\log{n}) ,然后我们考虑一种贪心的写法,已知m个段不一定要取满,所以一开始我们可以把相邻的同符号数字合并在一起,这样会生成一个新的正负交替的串….
然后一开始我们先选取所有的串,在可能的条件下我们要将串的数量减到m个,我们可以把所有串的绝对值存到一个set里面,然后每次从中取出一个最小的将其和其两端的合并(这里明显不能取在边缘的负数,将其舍弃比合并更加优秀),如果这是一个负数,他会把他两边的正数加在一起,然后让正数块减少一个,如果这是一个正数,由于此时他的绝对值最小,两边的数字与其相加是一个负数,这时正数块也减一.那么在经过若干次合并以后一定可以将块数减少到m个…
我们来思考这样是正确性.我们每次取一个绝对值最小的那么,我们可以保证此时他对之后的印象最小,然后我们意会一下,就可以了…..

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
const int N = 2e6 + 10;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL xx[N];
int n, m, now;
int pre[N],net[N],cnt = 0;
LL tmp = 0, ans = 0;
set<pair<LL, int> > Set;
void Erase(int x)
{
    int l = pre[x], r = net[x];
    if (l) net[l] = r;
    if (r) pre[r] = l;
}
int main()
{
    read(n), read(m);
    for (int i = 1, x; i <= n; ++i)
    {
        read(x);
        if ((tmp < 0 && x > 0) || (tmp > 0 && x < 0))
        {
            now += tmp > 0;
            xx[++cnt] = tmp;
            Set.insert(make_pair(abs(tmp), cnt));
            tmp = 0;
        }
        tmp += x;
        ans += x > 0 ? x : 0;
    }
    now += tmp > 0;
    xx[++cnt] = tmp;
    Set.insert(make_pair(abs(tmp), cnt));
    for (int i = 1; i <= cnt; ++i)
    {
        pre[i] = i - 1;
        net[i] = i + 1;
    }
    net[cnt] = xx[0] = 0;
    while (now > m)
    {
        int x = (*Set.begin()).second;
        Set.erase(Set.begin());
        if ((xx[x] < 0 && (!pre[x] || !net[x])) || !xx[x]) continue;
        Set.erase(make_pair(abs(xx[pre[x]]), pre[x]));
        Set.erase(make_pair(abs(xx[net[x]]), net[x]));
        ans -= abs(xx[x]);
        xx[x] = xx[x] + xx[pre[x]] + xx[net[x]];
        Erase(pre[x]);
        Erase(net[x]);
        Set.insert(make_pair(abs(xx[x]), x));
        now--;
    }
    printf("%lld\n", ans);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注