题目链接

关闭工位

题目描述

某工厂流水线上有 个工位。为了降低能耗，工厂决定恰好关闭其中 个工位。 关闭第 个工位（）会产生偏差值 。 限制条件：连续两个相邻工位不能同时关闭。 请你设计一个方案，在满足约束的前提下恰好关闭 个工位，使得总质量偏差最小。如果无法找到满足条件的关闭方案，则输出 。

解题思路

本题的本质是在一个长度为 的序列中，选取 个互不相邻的元素，使得它们的和最小。

  1. 可行性检查： 在一个长度为 的序列中，最多能选取的互不相邻元素的个数为 。如果 ，则无法完成任务，直接输出 。

  2. 贪心 + 反转代价（优先队列 + 双向链表）： 这是一个经典的“带反转的贪心”问题，也可以看作是求路图上的最小权 -独立集。

    • 使用优先队列（最小堆）存储所有当前可选的偏差值。
    • 每次取出堆顶最小的元素 。
    • 为了能够“反悔”，即将已选的 替换为其相邻的两个元素 和 ，我们将 加入总和后，将该位置的值更新为 。
    • 使用双向链表维护节点之间的左右关系，并用 deleted 标记位处理已合并的节点。
    • 在序列两端加入值为无穷大的哨兵节点，确保边界处理的正确性。

  3. 复杂度分析：

    • 时间复杂度：。
    • 空间复杂度：。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 节点结构体，用于双向链表
struct Node {
    long long val;
    int left, right;
    bool deleted;
};

// 堆元素结构体
struct HeapNode {
    long long val;
    int id;
    bool operator>(const HeapNode& other) const {
        return val > other.val;
    }
};

int main() {
    int t_total, k;
    cin >> t_total >> k;
    int n = t_total - 1;

    // 可行性检查
    if (k > (n + 1) / 2) {
        cout << -1 << endl;
        return 0;
    }
    if (k == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<Node> nodes(n + 2);
    priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode>> pq;

    // 偏差值从 1 到 n 填充，0 和 n+1 为无穷大哨兵
    long long INF = 1e15;
    nodes[0] = {INF, -1, 1, false};
    nodes[n + 1] = {INF, n, -1, false};

    for (int i = 1; i <= n; ++i) {
        long long v;
        cin >> v;
        nodes[i] = {v, i - 1, i + 1, false};
        pq.push({v, i});
    }

    long long total_deviation = 0;
    int count = 0;

    while (count < k) {
        HeapNode top = pq.top();
        pq.pop();

        int id = top.id;
        if (nodes[id].deleted) continue;

        total_deviation += nodes[id].val;
        count++;

        int l = nodes[id].left;
        int r = nodes[id].right;

        // 更新当前节点的值为反转代价：L + R - Current
        nodes[id].val = nodes[l].val + nodes[r].val - nodes[id].val;
        
        // 标记左右邻居已删除
        nodes[l].deleted = true;
        nodes[r].deleted = true;

        // 更新链表连接
        nodes[id].left = nodes[l].left;
        nodes[id].right = nodes[r].right;
        if (nodes[id].left != -1) nodes[nodes[id].left].right = id;
        if (nodes[id].right != -1) nodes[nodes[id].right].left = id;

        // 将新代价重新放入堆
        pq.push({nodes[id].val, id});
    }

    cout << total_deviation << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Node {
        long val;
        int left, right;
        boolean deleted;
        Node(long val, int left, int right) {
            this.val = val;
            this.left = left;
            this.right = right;
            this.deleted = false;
        }
    }

    static class HeapNode implements Comparable<HeapNode> {
        long val;
        int id;
        HeapNode(long val, int id) {
            this.val = val;
            this.id = id;
        }
        @Override
        public int compareTo(HeapNode other) {
            return Long.compare(this.val, other.val);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tTotal = sc.nextInt();
        int k = sc.nextInt();
        int n = tTotal - 1;

        if (k > (n + 1) / 2) {
            System.out.println("-1");
            return;
        }
        if (k == 0) {
            System.out.println("0");
            return;
        }

        Node[] nodes = new Node[n + 2];
        PriorityQueue<HeapNode> pq = new PriorityQueue<>();

        long INF = (long) 1e15;
        nodes[0] = new Node(INF, -1, 1);
        nodes[n + 1] = new Node(INF, n, -1);

        for (int i = 1; i <= n; i++) {
            long v = sc.nextLong();
            nodes[i] = new Node(v, i - 1, i + 1);
            pq.add(new HeapNode(v, i));
        }

        long totalDeviation = 0;
        int count = 0;

        while (count < k) {
            HeapNode top = pq.poll();
            int id = top.id;
            if (nodes[id].deleted) continue;

            totalDeviation += nodes[id].val;
            count++;

            int l = nodes[id].left;
            int r = nodes[id].right;

            nodes[id].val = nodes[l].val + nodes[r].val - nodes[id].val;
            nodes[l].deleted = true;
            nodes[r].deleted = true;

            nodes[id].left = nodes[l].left;
            nodes[id].right = nodes[r].right;
            if (nodes[id].left != -1) nodes[nodes[id].left].right = id;
            if (nodes[id].right != -1) nodes[nodes[id].right].left = id;

            pq.add(new HeapNode(nodes[id].val, id));
        }

        System.out.println(totalDeviation);
    }
}

import heapq

def solve():
    t_total = int(input())
    k = int(input())
    v_list = list(map(int, input().split()))

    n = t_total - 1
    
    if k > (n + 1) // 2:
        print("-1")
        return
    if k == 0:
        print("0")
        return

    actual_n = len(v_list)
    inf = 10**15
    nodes_val = [inf] + [float(v) for v in v_list] + [inf]
    left = list(range(-1, actual_n + 1))
    right = list(range(1, actual_n + 3))
    right[actual_n + 1] = -1
    deleted = [False] * (actual_n + 2)
    
    pq = []
    for i in range(1, actual_n + 1):
        heapq.heappush(pq, (nodes_val[i], i))
    
    ans = 0
    count = 0
    while count < k:
        val, i = heapq.heappop(pq)
        
        if deleted[i]:
            continue
            
        ans += val
        count += 1
        
        l, r = left[i], right[i]
        nodes_val[i] = nodes_val[l] + nodes_val[r] - nodes_val[i]
        deleted[l] = True
        deleted[r] = True
        
        left[i] = left[l]
        right[i] = right[r]
        if left[i] != -1:
            right[left[i]] = i
        if right[i] != -1:
            left[right[i]] = i
            
        heapq.heappush(pq, (nodes_val[i], i))
        
    print(int(ans))

solve()

算法及复杂度

  • 算法：贪心算法 + 反转代价（优先队列 + 双向链表维护独立集）。
  • 时间复杂度：。
  • 空间复杂度：。