2288.【POJ Challenge】生日礼物链表+堆+贪心

BZOJ2288 【POJ Challenge】生日礼物

题意：

给一个长度为\(n\)的数组，最多可以选\(m\)个连续段，问选取的最大值是多少

题解：

先把连续的符号相同的值合并，头和尾的负数去掉

然后如果正数的数量小于等于\(m\)的话，就直接输出正数的和

否则现在存在两种操作可以减少连续段数量

少选一个正数
选上两个正数之间的负数，把两边合并

显然不可能选相邻的一正一负

现在问题转化为选择\(k\)个不连续的数，使得其绝对值的和最小

然后就和这道题一样了：BZOJ1150 [CTSC2007]数据备份Backup

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 2e5+7;

int n,m,l[MAXN],r[MAXN];

bool used[MAXN];

vector<int> A;

int sgn(int x){ return x > 0 ? 1 : -1; }

struct cmp{

    bool operator () (const pair<int,int> x, const pair<int,int> y)const{

        return abs(x.first) > abs(y.first);

    }

};

int main(){

    ____();

    cin >> n >> m;

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

        int x; cin >> x;

        if(!x) continue;

        if(A.empty()){

            if(x<=0) continue;

            A.push_back(x);

        }

        else{

            if(sgn(x)==sgn(A.back())) A.back() += x;

            else A.push_back(x);

        }

    }

    if(!A.empty() and sgn(A.back())==-1) A.pop_back();

    int cnt = 0, ret = 0;

    for(int x : A) if(x>0) cnt++, ret += x;

    if(cnt<=m){

        cout << ret << endl;

        return 0;

    }

    A.insert(A.begin(),-1);

    priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> que;

    for(int i = 1; i < (int)A.size(); i++){

        que.push(make_pair(A[i],i));

        l[i] = i - 1; r[i] = i + 1;

    }

    r[A.size() - 1] = 0;

    cnt -= m;

    while(cnt--){

        while(used[que.top().second]) que.pop();

        auto p = que.top(); que.pop();

        ret -= abs(p.first);

        if(!l[p.second]) used[r[p.second]] = true, l[r[r[p.second]]] = 0;

        else if(!r[p.second]) used[l[p.second]] = true, r[l[l[p.second]]] = 0;

        else{

            A.push_back(A[l[p.second]] + A[r[p.second]] + A[p.second]);

            int now = A.size() - 1;

            que.push(make_pair(A.back(),now));

            used[l[p.second]] = used[r[p.second]] = true;

            l[now] = l[l[p.second]]; r[now] = r[r[p.second]];

            if(l[l[p.second]]) r[l[l[p.second]]] = now;

            if(r[r[p.second]]) l[r[r[p.second]]] = now;

        }

    }

    cout << ret << endl;

    return 0;

}

巴特西

2288.【POJ Challenge】生日礼物链表+堆+贪心

题意：

题解：

最新文章

热门文章

巴特西

2288.【POJ Challenge】生日礼物 链表+堆+贪心

题意：

题解：

最新文章

热门文章

2288.【POJ Challenge】生日礼物链表+堆+贪心