国家集训队 种树

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

Description

有一个环形广场上有 $n$ 个种树位置，顺时针编号 1 到 $n$。每个位置有美观度 $A_i$，选取不相邻的 $m$ 个位置种树，求最大美观度和。

Solution

思路同APIO/CTSC 2007 数据备份，只不过需通过环形链表解决，且当 $n / 2 < m$ 时无解。

Code

环形双向链表

与非环形双向链表不同，$head$ 与 $tail$ 不用作为虚拟节点。链表建立时 $tail->next = head$ 且 $head->prev = tail$。删除和插入操作与非双向链表类似。

环形双向链表

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 2e5 + 5;

int n, m, a[MAXN], cnt, ans;

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;
    int data = 0, id = -1;
};
map<int, bool> deleted;
priority_queue<ListNode> q;

struct CycleList {
    CycleList() = default;

    ListNode* insert(int data, int id) {
        auto newNode = new ListNode();
        newNode->data = data, newNode->id = id, newNode->cur = newNode;
        if (head == NULL) head = tail = newNode;
        newNode->prev = tail, tail->next = newNode, tail = newNode;
        tail->next = head, head->prev = tail;
        return newNode;
    }

    ListNode* erase(ListNode* cur) {
        auto prev = cur->prev, next = cur->next;
        int data = prev->data + next->data - cur->data;
        deleted[prev->id] = deleted[cur->id] = deleted[next->id] = true;
        
        auto newNode = new ListNode();
        newNode->data = data, newNode->id = cnt++, newNode->cur = newNode;
        prev->prev->next = newNode, newNode->prev = prev->prev;
        next->next->prev = newNode, newNode->next = next->next;
        return newNode;
    }

    ListNode *head = NULL, *tail = NULL;
} lst;

void calcA(int tot = 0) {
    while (!q.empty() && tot < m) {
        auto cur = q.top();
        q.pop();
        if (deleted[cur.id]) continue;
        ans += cur.data, tot++;
        auto newNode = lst.erase(cur.cur);
        q.push(*newNode);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    if (n / 2 < m) return printf("Error!\n"), 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        auto newNode = i == n - 1 ? lst.insert(a[i], cnt++) : lst.insert(a[i], cnt++);
        q.push(*newNode);
    }
    calcA();
    printf("%d\n", ans);
    return 0;
}

STL 环形链表

$STL$ 的 $list$ 是环形链表。list.end() 的下一个迭代器是 list.begin()，list.begin() 的上一个迭代器是 list.end()。删除过程中，需特判当前迭代器是否为 list.end()，若是，则选取下一个迭代器进行删除。另外需注意：由于最后一次删除操作可能导致 $list$ 为空，要特判一下。

STL 环形链表

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 2e5 + 5;

int n, m, a[MAXN], ans, cnt;

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

inline void calcA(int tot = 0) {
    while (!q.empty() && tot < m) {
        auto cur = q.top();
        q.pop();
        if (deleted[cur.id]) continue;
        ans += cur.data, tot++;
        if (tot == m) break;
        //将相邻三个节点删除 并用新节点替换 带反悔贪心
        int data(0);
        auto itr = --cur.itr;
        if (itr == lst.end()) --itr;

        data += itr->data, deleted[itr->id] = true, itr = lst.erase(itr);
        if (itr == lst.end()) ++itr;

        data -= itr->data, deleted[itr->id] = true, itr = lst.erase(itr);
        if (itr == lst.end()) ++itr;

        if (itr == lst.end()) cout << "err" << endl;
        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() {
    scanf("%d %d", &n, &m);
    if (n / 2 < m) return printf("Error!\n"), 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        auto newNode = ListNode(a[i], cnt++);
        newNode.itr = lst.insert(lst.end(), newNode); //末尾插入
        q.push(newNode); //加入优先队列
    } 
    calcA(); //计算美观度sigma_Ai
    printf("%d\n", ans);
    return 0;
}