APIO/CTSC 2007 数据备份

发表于2020-07-17更新于2023-09-15字数统计1.5k阅读时长13分

数据备份

  • 题目链接
  • 数据结构/优先队列/链表
  • STL/list
  • 贪心

Description

有 NN 座办公楼位于同一条街上，已知每座办公楼距离大街起点的距离。现要用 KK 条网络电缆将办公楼连接，且任意一个办公楼都属于唯一配对组(即连接的 2K2K 个办公楼一定是相异的)。求 KK 条网络电缆最小的长度总和。

Solution

容易发现，最优解中每两个配对的办公楼一定是相邻的。于是先求出两个相邻办公楼之间的距离，记为 D1,D2,D3,...,DN−1D_1, D_2, D_3, ..., D_{N - 1}。于是问题可以转化为：从数列 DD 中选取不超过 KK 个不相邻的数，使它们的和最小。

考虑贪心：

  • 如果 K=1K=1，答案显然是数列 D 中的最小值
  • 如果 K=2K=2，可以证明答案是以下两种情况之一：
    • 选取 DiD_i，以及除了 Di−1,Di,Di+1D_{i-1}, D_i, D_{i+1} 之外其他数中的最小值
    • 选取最小值 DiD_i左右两侧的两个数，即 Di−1D_{i-1} 和 Di+1D_{i+1}
    • 即最优解中，最小值左右两侧的数要么选，要么都不选
  • 为防止选取局部最优解，可以先选取数列 DD 中的最小值 DiD_i，然后把 Di−1,Di,Di+1D_{i-1}, D_i, D_{i+1} 删除，把 Di−1+Di+1−DiD_{i-1}+D_{i+1}-D_i 插入到数列 DD 中之前执行删除的位置。这样如果之后选了 Di−1+Di+1−DiD_{i-1}+D_{i+1}-D_i，相当于没有选 DiD_i，换上了 Di−1D_{i-1} 和 Di+1D_{i+1}。

于是可建立一个初始有 N−1N-1 个节点的链表，链表节点记录数值 DiD_i，节点编号 IdiId_i，以及链表节点指针或对应的迭代器。再建立一个优先队列(小根堆)，将链表节点存入。K 次操作中，取出堆顶的链表节点 ListNodeListNode，在链表中删除 ListNode−>prevListNode->prev 和 ListNode−>nextListNode->next，并创建新节点(数值为 ListNode−>prev−>data+ListNode−>next−>data−ListNode−>dataListNode->prev->data+ListNode->next->data-ListNode->data)插入链表和优先队列。

注意：为防止越界或简化边界情况判断，可以在链表起始和末尾插入极大值。

Code

指针版双向链表

指针版双向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 1e5 + 5;
constexpr LL INF = 1e18;

LL n, k, dis[MAXN], ans, cnt;

struct ListNode {
    ListNode() = default;
    bool operator<(const ListNode &other) const {
        return this->data == other.data ? this->id > other.id : this->data > other.data;
    }
    ListNode *prev = NULL, *next = NULL, *cur = NULL;
    LL data = 0, id = -1;
};
map<int, bool> deleted;

struct List {
    List() { //构造函数
        this->head = new ListNode(), this->tail = new ListNode();
        this->head->next = this->tail;
        this->tail->prev = this->head;
    }

    ListNode *insert(LL data) { //插入值，返回节点指针
        ListNode *cur = new ListNode();
        cur->data = data, cur->id = cnt++, cur->cur = cur;
        tail->prev->next = cur, cur->prev = tail->prev;
        cur->next = tail, tail->prev = cur;
        return cur;
    }

    ListNode *erase(ListNode *cur) { //删除节点，返回新节点指针
        LL data = cur->prev->data + cur->next->data - cur->data;
        ListNode *newListNode = new ListNode();
        newListNode->cur = newListNode;
        newListNode->data = data, newListNode->id = cnt++;

        ListNode *prev = cur->prev, *next = cur->next;
        prev->prev->next = newListNode, newListNode->prev = prev->prev;
        next->next->prev = newListNode, newListNode->next = next->next;

        deleted[prev->id] = deleted[next->id] = deleted[cur->id] = true;
        return newListNode;
    }

    ~List() {}
    ListNode *head = NULL, *tail = NULL;
} lst;

priority_queue<ListNode> q;
inline void calcLen(int tot = 0) {
    while (!q.empty() && tot < k) {
        ListNode* cur = q.top().cur;
        q.pop();
        if (deleted[cur->id]) continue;
        ans += cur->data, tot++;
        ListNode *newListNode = lst.erase(cur);
        q.push(*newListNode); //插入新节点
    }
}

int main() {
    scanf("%lld %lld", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%lld", dis + i);
    lst.insert(INF); //防止越界 简化边界判断
    for (int i = 0; i < n - 1; ++i) q.push(*lst.insert(dis[i + 1] - dis[i]));
    lst.insert(INF); //防止越界 简化边界判断
    calcLen(); //计算总长度
    printf("%lld\n", ans);
    return 0;
}

STL list

STLSTL 的 listlist 为 环形双向链表, 本题中用到以下功能。

  • 通过 iterator−−iterator-- 或 iterator++iterator++ 获得 prevprev 或 nextnext 的迭代器。
  • insert() 成员函数在指定位置处插入值，并返回插入的元素所对应的的迭代器
  • erase() 成员函数对指定位置进行删除，返回删除的元素后一个位置的迭代器
STL list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 1e5 + 5;
constexpr LL INF = 1e15;

LL n, k, dis[MAXN], ans, cnt;

struct ListNode {
    ListNode() = default;
    ListNode(LL _data, LL _id) : data(_data), id(_id) {}
    bool operator<(const ListNode &other) const {
        return this->data == other.data ? this->id > other.id : this->data > other.data;
    }
    LL data = INF, id = -1;
    list<ListNode>::iterator itr;
};
list<ListNode> lst;
priority_queue<ListNode> q;
map<LL, bool> deleted;

inline void calcLen(int tot = 0) {
    while (!q.empty() && tot < k) {
        auto cur = q.top();
        q.pop();
        if (deleted[cur.id]) continue;
        ans += cur.data, tot++;
        //删除
        auto itr = cur.itr;
        --itr; //得到cur->prev的迭代器
        LL data = itr->data; deleted[itr->id] = true, itr = lst.erase(itr);
        data -= itr->data, deleted[itr->id] = true, itr = lst.erase(itr);
        data += itr->data, deleted[itr->id] = true, itr = lst.erase(itr);
        //删除
        auto newNode = ListNode(data, cnt++);
        newNode.itr = lst.insert(itr, newNode);
        q.push(newNode);
    }
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> dis[i];
    lst.emplace_back(ListNode(INF, cnt++)); //防止越界 简化边界判断
    for (int i = 0; i < n - 1; ++i) {
        auto newNode = ListNode(dis[i + 1] - dis[i], cnt++);
        newNode.itr = lst.insert(lst.end(), newNode); //末尾插入
        q.push(newNode);
    }
    lst.emplace_back(ListNode(INF, cnt++)); //防止越界 简化边界判断
    calcLen();
    cout << ans << endl;
    return 0;
}

类似题目

种树
国家集训队 种树
BACKUP Backup Files