生日礼物

题目

翰翰18岁生日的时候,达达给她看了一个神奇的序列 A1,A2,…,AN。

她被允许从中选择不超过 M 个连续的部分作为自己的生日礼物。

翰翰想要知道选择元素之和的最大值。

你能帮助她吗?

输入格式

第一行包含两个整数N,M。

第二行包含N个整数A1~AN。

输出格式

输出一个整数,表示答案。

数据范围

1≤N,M≤105,
|Ai|≤104

输入样例:

5 2 
2 -3 2 -1 2

输出样例:

5

分析

  • 我们可以将原数组分为若干个段,每段都是正数或者都是负数;
  • 如果正数的段数为t1,负数的段数为t2,那么当t1<m时,我们可以直接选择这t1段正数即可,当t1>m时,我们就要开始分情况讨论了。
  • 我们可以先加这t1段的值全部加上,然后从中删除t1-m段即可,即从t1段中选择t1-m最小的段删除,但是删除的时候我们可以使用合并的方式,即将中间那段负数加进来,我们发现这个问题已经转化为了上次写的另一篇题解
  • 数据备份:https://jzenghui.top/2019/08/29/shu-ju-bei-fen/
  • 那我们使用他的解法解决剩下的步骤即可。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N=100010;

int n, m;
int a[N],l[N],r[N];
bool st[N];

void remove(int p) {
    // 从链表中删去
    l[r[p]] = l[p];
    r[l[p]] = r[p];
    // 从heap里删去
    st[p] = true;
}

int main() {
    cin >> n >> m;

    int k = 1;
    for (int i = 0; i < n; i ++ ) {
        int x;
        cin >> x;
        if ((long long)a[k] * x < 0) a[ ++ k] = x;
        else a[k] += x;
    }

    n = k;
    int cnt = 0, res = 0;
    for (int i = 1; i <= n; i ++ )
        if (a[i] > 0) {
            cnt ++ ;
            res += a[i];
        }

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (int i = 1; i <= n; i ++ ) { //初始化链表
        l[i] = i - 1;
        r[i] = i + 1;
        heap.push({abs(a[i]), i});
    }

    while (cnt > m) {
        while (st[heap.top().second]) heap.pop();
        auto t = heap.top();
        heap.pop();
        int v = t.first, p = t.second;
        if (l[p] != 0 && r[p] != n + 1 || a[p] > 0) {//判断边界 
            cnt -- ;
            res -= v;
            int left = l[p], right = r[p];
            a[p] += a[left] + a[right];
            heap.push({abs(a[p]), p});
            remove(left);
            remove(right);
        }
    }

    cout << res << endl;
    return 0;
}

   转载规则


《生日礼物》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录