「Bzoj 1150」「CTSC2007」数据备份Backup (贪心+堆+链表+差分)

发表于 | 分类于 | | + s

Bzoj 1150
题意：见上。
很容易发现最优配对一定是相邻的，因为反应序列数据相对关系的是差分序列，所以我们在差分序列上找$k$个最小和不相邻点即为答案。

现在问题就是直接取最小值可能没有取最小值两边的数更优，那么我们可以先取最小值，然后之后考虑怎么反悔。参照低买高卖那题，那题先买，如果后面有更优的，那么在这个基础上继续买卖可以得到最优解。这里先取了最小值，那么如果不优，最小值两边的数一定必取，因为如果只选一边选最小值最优。我们要添加一个元素在中间，使得之后选这个点相当于返回选了两边的数。那么用链表支持这个操作。由于是全局最小值，很容易发现可以用堆来维护最小值，注意堆和链表要同步，相当于映射关系。

注意链表有误，要将第一个点插在 $h$ 后面

1、链表不可达点的赋值
2、在分析贪心策略时，运用了渐进思想中的从变量小开始思考
3、贪心错误时修改贪心，多分支哈夫曼树解决方法亦如此
4、要尽可能将问题转化为数学模型，序列问题

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    struct data {
        int pos;
        LL w;
        bool operator < (const data &rhs) const {
            return w > rhs.w;
        }
    };

    int n, k, a[MAXN], d[MAXN];
    int tot, l[MAXN * 3], r[MAXN * 3], h, t, vis[MAXN * 3];
    LL val[MAXN * 3];

    priority_queue<data > q;

    void ins(int pos, LL v) {
        ++tot, val[tot] = v, l[tot] = pos, r[tot] = r[pos];
        l[r[pos]] = tot;
        r[pos] = tot;
    }
    void del(int pos) {
        vis[pos] = 1;
        r[l[pos]] = r[pos], l[r[pos]] = l[pos];
    }

    void clean() {
        ms(vis, 0);
        tot = 2, h = 1, t = 2, l[t] = h, r[h] = t;
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        val[0] = val[1] = val[2] = 4223372036854775807ll;
        for (int i = 1; i < n; ++i) d[i] = a[i + 1] - a[i];
        ins(h, d[1]), q.push((data){tot, d[1]});
          for (int i = 2; i < n; ++i) ins(2 + i - 1, d[i]), q.push((data){tot, d[i]});
        //for (int i = 1; i < n; ++i) ins(2 + i - 1, d[i]), q.push((data){tot, d[i]}); // 这样插有问题
        LL ans = 0;
        int o = 0;
        while (1) {
            data p = q.top(); q.pop();
            if (vis[p.pos]) continue ;
            ++o;
            ans += p.w;
            val[p.pos] = val[l[p.pos]] + val[r[p.pos]] - val[p.pos];
            del(l[p.pos]), del(r[p.pos]);
            q.push((data){p.pos, val[p.pos]});
            if (o >= k) break;
        }
        printf("%lld\n", ans);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
10 5
1
3
8
11
15
20
25
35
40
58
*/
------ 本文结束 ------