双向链表

前言

第一次接触这玩意儿，所以记录一下。

题目

[国家集训队] 种树

题目描述

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。

园林部门得到指令后，初步规划出 \(n\) 个种树的位置，顺时针编号 \(1\) 到 \(n\)。并且每个位置都有一个美观度 \(A_i\)，如果在这里种树就可以得到这 \(A_i\) 的美观度。但由于 \(A\) 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（\(i\) 号位置和 \(i+1\) 号位置叫相邻位置。值得注意的是 \(1\) 号和 \(n\) 号也算相邻位置）。

最终市政府给园林部门提供了 \(m\) 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 \(m\) 棵树苗全部种上，给出无解信息。

输入格式

输入的第一行包含两个正整数 \(n\)，\(m\)。

第二行 \(n\) 个整数，第 \(i\) 个代表 \(A_i\)。

输出格式

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出 Error!。

样例 #1

样例输入 #1

7 3
1 2 3 4 5 6 7

样例输出 #1

15

样例 #2

样例输入 #2

7 4
1 2 3 4 5 6 7

样例输出 #2

Error!

提示

对于全部数据：\(m\le n\)，\(-1000\le A_i\le1000\)。

题目分析。

这是一道可反悔贪心 + 双向链表的题。

• 一、可反悔贪心
  题目中说，一个树选了旁边两个数就不能选，比如下图。
  

我们肯定先选 \(9\)，然后 \(8\)、\(8\) 不能选，所以最后答案是 \(9+1=10\)。但是这题最优解显然是 \(8+8=16\)。

我们肯定会想到用可反悔贪心，用大根堆。

但是我们无法比较，来进行反悔。

于是我们想了一个办法。第一次选 \(9\) 时将 \(8+8-9=7\) 加入这个大根堆。我们不妨来模拟一下。

首先 \(ans\) 加 \(9\)，然后删去 \(8\)、\(8\)， \(7\) 于队列。

后出 \(8\)，被删了，跳过，然后就弹出 \(7\) 了，\(ans\) 加上 \(7\)，把两边剔除，

于是答案就是 \(9+7=16\)，我们发现和 \(8+8=16\) 结果一样。

• 二、如何用双向链表删点。

中间的为 \(x\)，我们只要让 [p[x].lft].rgt = p[x].rgt,[x].rgt].lft = p[x].lft

然后分别令 \(x\) 为 p[x].lft 和 p[x].rgt` 就行了。

代码

/*
    Author: Rainypaster(lhy)
    Time: 03/10/2024
    File: P1972.cpp
    Email: [email protected]
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace IO
{
    template<typename T>
    T read(T x)
    {
        T sum = 0, opt = 1;
        char ch = getchar();
        while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
        while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
        return sum * opt;
    }

}
#define read IO::read(0)
#define rep(i, n) for(int i = 1; i <= n; i ++)
#define repa(i, n) for(int i = 0; i < n; i ++)
#define repb(i, n) for(int i = 1; i <= n; i ++)
#define repc(i, n) for(int i = 0; i < n; i ++)
#define lson (u << 1)
#define rson (u << 1 | 1)
#define gcd(a, b) __gcd(a, b)

const int N = 2e5 + 5;

struct Node{
	int val,id;
	bool operator <(Node it) const{
		return val < it.val;
	}
};

priority_queue<Node> q;
struct node
{
    int val, lft, rgt;
}p[N];

bool vis[N];

int ans;

void delt(int x)
{
    p[p[x].lft].rgt = p[x].rgt;
    p[p[x].rgt].lft = p[x].lft;
}

void solve()
{
    int n = read, m = read;
    if(n / 2 < m) {
        puts("Error!");
        return ;
    }
    for(int i = 1;i <= n;i ++ ){
        p[i].val = read;
        p[i].lft = i - 1;
        p[i].rgt = i + 1;
        q.push({p[i].val, i});
    }
    p[1].lft = n, p[n].rgt = 1;

    for(int i = 1;i <= m;i ++ ){
        while(vis[q.top().id]) q.pop();
        Node now = q.top();
        q.pop();
        vis[p[now.id].lft] = vis[p[now.id].rgt] = true;
        p[now.id].val = p[p[now.id].lft].val + p[p[now.id].rgt].val - p[now.id].val;
        ans += now.val;
        q.push({p[now.id].val, now.id});
        delt(p[now.id].lft), delt(p[now.id].rgt);
    }
    cout << ans << endl;
}

signed main()
{
    int T = 1;
    while(T -- ) solve();
    return 0;
}