(TIOJ) 2039 . AI-666 賺多少 [GREEDY]

https://tioj.ck.tp.edu.tw/problems/2039

先說，下面是82分的 N log N greedy解。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

typedef pair<LL,LL> pii;
const int N = 2000006;
const LL INF = (1LL<<50);

LL a[N];

#define SZ(x) ((int)(x).size())
#define F first
#define S second

LL s[N];

int lc[N];
int rc[N];

LL cost[N];

bool dead[N];

int main ()
{
    int n,k;
    scanf("%d %d",&n,&k);
    vector<LL> v;
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&a[i]);
        if (i > 1)
        {
            int _ = a[i] - a[i-1];
            if (_ > 0)
            {
                if (v.empty())
                {
                    v.push_back(_);
                }
                else if (v.back() > 0)
                {
                    v[ SZ(v)-1 ] += _;
                }
                else if (v.back() < 0)
                {
                    v.push_back(_);
                }
            }
            else if (_ < 0)
            {
                if (v.empty()) ;
                else if (v.back() > 0)
                {
                    v.push_back(_);
                }
                else if (v.back() < 0)
                {
                    v[ SZ(v)-1 ] += _;
                }
            }
        }
    }
    if (!v.empty() && v.back() < 0) v.pop_back();
    long long tot=0;
    int b=0;
    for (int i:v)
    {
        if (i>0)
        {
            tot += i;
            ++b;
        }
    }
    if (b<=k)
    {
        printf("%lld\n",tot);
        return 0;
    }
    int nn = SZ(v);
    s[0] = s[nn+1] = 0;
    for (int i=1;nn>=i;i++)
    {
        s[i] = abs(v[i-1]);
        lc[i] = i-1;
        rc[i] = i+1;
        cost[i] = s[i];
    }
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for (int i=1;nn>=i;i++)
    {
        pq.push(make_pair(cost[i],i));
        //cout << "cost = " << cost[i] << " , i = " << i << endl;
    }
    while (!pq.empty() && b > k)
    {
        pii p=pq.top();
        pq.pop();
        if (dead[p.S]) continue;
        //cout << "p = (" << p.F<< " , " << p.S << " )" << endl;
        --b;
        tot -= p.F;
        int mid = p.S;
        int l = lc[mid];
        int r = rc[mid];
        cost[mid] = cost[l] + cost[r] - cost[mid];
        if (l != 0 && r != nn+1) pq.push(make_pair(cost[mid],mid));
        else dead[mid] = true;
        dead[l] = true;
        dead[r] = true;
        lc[mid] = lc[l];
        rc[mid] = rc[r];
        //cout << "l = " << l << " , r = " << r << endl;
        rc[ lc[l] ] = (r != nn+1?mid:nn+1);
        lc[ rc[r] ] = (l != 0?mid:0);
        /*
        for (int i=1;nn>=i;i++)
        {
            cout << "i = " << i << " , cost = " <<cost[i] << " , dead = " << dead[i] << " , lc = " << lc[i] << " , rc = " << rc[i] << endl;
        }*/

        //cout << endl << endl;
    }
    printf("%lld\n",tot);
}