解题思路

本题要求两名管理员交替从当前“存活”的书中挑选：

• 小张每次选全局最轻（若并列取最左）
• 小李每次选全局最重（若并列取最右） 然后以该书为中心，向左右各扩展至多 k 本，一并移除。这个“左右”始终是相对当前尚未被移除的相邻关系。

要高效实现，需要同时解决两个核心操作：

1. 快速找到当前最轻/最重且仍未被移除的书

   • 用两个堆（优先队列）分别维护：

     • 最小堆：键为 (重量, 位置)，并列时位置小的优先（最左）。
     • 最大堆：键为 (-重量, -位置)，并列时位置大的优先（最右）。

   • 采用惰性删除：堆顶若已被移除则反复弹出，直到堆顶为有效元素。

2. 从选中的中心位置向两侧各扩展 k 本并整体移除

   • 用数组实现的双向链表维护当前存活的相邻关系： prev[i] 表示当前位置左侧仍存活的邻居下标，next[i] 表示右侧邻居。
   • 选中下标 i 后，先向左走 k 步（或走到最左），得到左端点 L； 再向右走 k 步（或走到最右），得到右端点 R。 将 [L, R] 这段在双向链表上整段移除，并把中间每本书标记归属给当轮玩家。
   • 维护链表连边：把 prev[L] 与 next[R] 连接起来。

以上做法的关键是：每本书恰好被删除一次，尽管我们会在堆里多次遇到已删除元素，但总弹出次数线性级，整体复杂度可控。

复杂度分析

• 每本书最多：

  • 被堆弹出（有效一次，失效若干次，但总体仍是线性摊还）；
  • 在双向链表中被访问并删除一次。

• 因此总体时间复杂度为 O(n log n)（主要来自堆操作），空间复杂度为 O(n)（堆、链表、标记与结果存储）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
import heapq

# 功能函数：根据题意进行模拟，返回两位管理员分别搬走的编号（升序）
def solve_books(n, k, a):
    # 1-based 索引
    a = [0] + a

    # 活跃标记：True 表示尚未被移除
    alive = [True] * (n + 1)

    # 记录归属：0=未归属，1=小张，2=小李
    owner = [0] * (n + 1)

    # 双向链表（数组实现），0 作为哨兵（无效端）
    prev = [0] * (n + 1)
    next = [0] * (n + 1)
    for i in range(1, n + 1):
        prev[i] = i - 1 if i > 1 else 0
        next[i] = i + 1 if i < n else 0

    # 两个堆：最小堆（重量小/位置小优先），最大堆（重量大/位置大优先）
    min_heap = []  # (a[i], i)
    max_heap = []  # (-a[i], -i) 使得重量大优先，且并列时 i 大的优先
    for i in range(1, n + 1):
        heapq.heappush(min_heap, (a[i], i))
        heapq.heappush(max_heap, (-a[i], -i))

    remain = n
    turn = 1  # 1 表示小张，2 表示小李

    while remain > 0:
        if turn == 1:
            # 小张：取最小堆
            while min_heap:
                w, idx = heapq.heappop(min_heap)
                if alive[idx] and a[idx] == w:
                    center = idx
                    break
            else:
                break
        else:
            # 小李：取最大堆
            while max_heap:
                nw, ni = heapq.heappop(max_heap)
                w, idx = -nw, -ni
                if alive[idx] and a[idx] == w:
                    center = idx
                    break
            else:
                break

        # 以 center 为中心，向左、右各扩展 k 本（在当前链表中）
        # 找左端点 L
        L = center
        steps = 0
        while steps < k and prev[L] != 0:
            L = prev[L]
            steps += 1
        # 找右端点 R
        R = center
        steps = 0
        while steps < k and next[R] != 0:
            R = next[R]
            steps += 1

        # 记录待链接的外侧邻居
        left_out = prev[L]
        right_out = next[R]

        # 删除 [L..R] 闭区间（沿链表遍历）
        cur = L
        while True:
            alive[cur] = False
            owner[cur] = turn
            remain -= 1
            if cur == R:
                break
            cur = next[cur]

        # 重新连接链表
        if left_out != 0:
            next[left_out] = right_out
        if right_out != 0:
            prev[right_out] = left_out

        # 交换回合
        turn = 2 if turn == 1 else 1

    # 汇总结果并升序输出
    zhang = [i for i in range(1, n + 1) if owner[i] == 1]
    li = [i for i in range(1, n + 1) if owner[i] == 2]
    zhang.sort()
    li.sort()
    return zhang, li


def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2+n]))
    zhang, li = solve_books(n, k, a)
    print(" ".join(map(str, zhang)))
    print(" ".join(map(str, li)))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名固定为 Main
// 思路：双堆（惰性删除）+ 数组双向链表，整体 O(n log n)
import java.io.*;
import java.util.*;

public class Main {
    // 记录一本书
    static class Node {
        int w;  // 重量
        int i;  // 位置（1-based）
        Node(int w, int i) { this.w = w; this.i = i; }
    }

    // 主逻辑：返回两位玩家搬走的编号（升序）
    static List<List<Integer>> solveBooks(int n, int k, int[] a) {
        // alive: 是否仍在书架
        boolean[] alive = new boolean[n + 1];
        Arrays.fill(alive, true);

        // owner: 0 未归属，1 小张，2 小李
        int[] owner = new int[n + 1];

        // 双向链表
        int[] prev = new int[n + 1];
        int[] next = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prev[i] = (i == 1 ? 0 : i - 1);
            next[i] = (i == n ? 0 : i + 1);
        }

        // 最小堆（重量小优先，位置小优先）
        PriorityQueue<Node> minHeap = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node x, Node y) {
                if (x.w != y.w) return Integer.compare(x.w, y.w);
                return Integer.compare(x.i, y.i);
            }
        });
        // 最大堆（重量大优先；并列时位置大优先）
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node x, Node y) {
                if (x.w != y.w) return Integer.compare(y.w, x.w); // 重量降序
                return Integer.compare(y.i, x.i); // 位置降序（右侧优先）
            }
        });

        for (int i = 1; i <= n; i++) {
            minHeap.add(new Node(a[i], i));
            maxHeap.add(new Node(a[i], i));
        }

        int remain = n;
        int turn = 1; // 1=张，2=李

        while (remain > 0) {
            int center = -1;
            if (turn == 1) {
                // 小张：取最小堆
                while (!minHeap.isEmpty()) {
                    Node top = minHeap.poll();
                    if (alive[top.i] && a[top.i] == top.w) {
                        center = top.i;
                        break;
                    }
                }
            } else {
                // 小李：取最大堆
                while (!maxHeap.isEmpty()) {
                    Node top = maxHeap.poll();
                    if (alive[top.i] && a[top.i] == top.w) {
                        center = top.i;
                        break;
                    }
                }
            }
            if (center == -1) break;

            // 找左端点 L
            int L = center;
            int steps = 0;
            while (steps < k && prev[L] != 0) {
                L = prev[L];
                steps++;
            }
            // 找右端点 R
            int R = center;
            steps = 0;
            while (steps < k && next[R] != 0) {
                R = next[R];
                steps++;
            }

            int leftOut = prev[L];
            int rightOut = next[R];

            // 删除 [L..R]
            int cur = L;
            while (true) {
                alive[cur] = false;
                owner[cur] = turn;
                remain--;
                if (cur == R) break;
                cur = next[cur];
            }

            // 重新连边
            if (leftOut != 0) next[leftOut] = rightOut;
            if (rightOut != 0) prev[rightOut] = leftOut;

            // 交换回合
            turn = (turn == 1 ? 2 : 1);
        }

        List<Integer> zhang = new ArrayList<>();
        List<Integer> li = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (owner[i] == 1) zhang.add(i);
            else if (owner[i] == 2) li.add(i);
        }
        Collections.sort(zhang);
        Collections.sort(li);

        List<List<Integer>> ans = new ArrayList<>();
        ans.add(zhang);
        ans.add(li);
        return ans;
    }

    // 简单快速读入（基于缓冲输入）
    static class FastReader {
        BufferedInputStream in = new BufferedInputStream(System.in);
        byte[] buffer = new byte[1 << 16];
        int ptr = 0, len = 0;

        int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, s = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { s = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * s;
        }
    }

    public static void main(String[] args) throws Exception {
        FastReader fr = new FastReader();
        int n = fr.nextInt();
        int k = fr.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = fr.nextInt();

        List<List<Integer>> ans = solveBooks(n, k, a);
        List<Integer> zhang = ans.get(0);
        List<Integer> li = ans.get(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < zhang.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(zhang.get(i));
        }
        System.out.println(sb.toString());
        sb.setLength(0);
        for (int i = 0; i < li.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(li.get(i));
        }
        System.out.println(sb.toString());
    }
}

C++

// ACM 风格，主函数读取输入，核心逻辑在外部函数
// 思路：两个优先队列（惰性删除）+ 数组双向链表
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int w, i; // 重量与位置
};

// 自定义比较器
struct MinCmp { // 最小堆：重量小优先，位置小优先
    bool operator()(const Node& a, const Node& b) const {
        if (a.w != b.w) return a.w > b.w;      // 小顶堆效果
        return a.i > b.i;
    }
};
struct MaxCmp { // 最大堆：重量大优先；并列时位置大优先
    bool operator()(const Node& a, const Node& b) const {
        if (a.w != b.w) return a.w < b.w;      // 大顶堆效果
        return a.i < b.i;                      // 位置大优先
    }
};

// 功能函数：返回两人搬走的编号（升序）
pair<vector<int>, vector<int>> solve_books(int n, int k, const vector<int>& a1) {
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) a[i] = a1[i];

    vector<char> alive(n + 1, 1); // 是否还在书架
    vector<int> owner(n + 1, 0);  // 归属：0/1/2

    // 双向链表
    vector<int> prev(n + 1), nxt(n + 1);
    for (int i = 1; i <= n; ++i) {
        prev[i] = (i == 1 ? 0 : i - 1);
        nxt[i] = (i == n ? 0 : i + 1);
    }

    priority_queue<Node, vector<Node>, MinCmp> minHeap;
    priority_queue<Node, vector<Node>, MaxCmp> maxHeap;
    for (int i = 1; i <= n; ++i) {
        minHeap.push({a[i], i});
        maxHeap.push({a[i], i});
    }

    int remain = n;
    int turn = 1; // 1=张，2=李

    while (remain > 0) {
        int center = -1;
        if (turn == 1) {
            // 小张：取最小堆
            while (!minHeap.empty()) {
                Node top = minHeap.top(); minHeap.pop();
                if (alive[top.i] && a[top.i] == top.w) {
                    center = top.i; break;
                }
            }
        } else {
            // 小李：取最大堆
            while (!maxHeap.empty()) {
                Node top = maxHeap.top(); maxHeap.pop();
                if (alive[top.i] && a[top.i] == top.w) {
                    center = top.i; break;
                }
            }
        }
        if (center == -1) break;

        // 找左端 L
        int L = center, steps = 0;
        while (steps < k && prev[L] != 0) { L = prev[L]; ++steps; }
        // 找右端 R
        int R = center; steps = 0;
        while (steps < k && nxt[R] != 0) { R = nxt[R]; ++steps; }

        int leftOut = prev[L], rightOut = nxt[R];

        // 删除 [L..R]
        int cur = L;
        while (true) {
            alive[cur] = 0;
            owner[cur] = turn;
            --remain;
            if (cur == R) break;
            cur = nxt[cur];
        }

        // 重新连边
        if (leftOut != 0) nxt[leftOut] = rightOut;
        if (rightOut != 0) prev[rightOut] = leftOut;

        // 交换回合
        turn = (turn == 1 ? 2 : 1);
    }

    vector<int> zhang, li;
    for (int i = 1; i <= n; ++i) {
        if (owner[i] == 1) zhang.push_back(i);
        else if (owner[i] == 2) li.push_back(i);
    }
    sort(zhang.begin(), zhang.end());
    sort(li.begin(), li.end());
    return {zhang, li};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    auto res = solve_books(n, k, a);
    auto& zhang = res.first;
    auto& li = res.second;

    for (int i = 0; i < (int)zhang.size(); ++i) {
        if (i) cout << ' ';
        cout << zhang[i];
    }
    cout << "\n";
    for (int i = 0; i < (int)li.size(); ++i) {
        if (i) cout << ' ';
        cout << li[i];
    }
    cout << "\n";
    return 0;
}

题目内容

图书馆有 $n$ 本书横向排成一排，从左到右编号为 $1$ 到 $n$ ，每本书的重量为 $a_i$ 千克。图书管理员小张和小李轮流整理这些书籍，规则如下：

首先是小张整理，小张的策略是找到当前书架上最轻的一本书(如果有多个重量相同，则选择最左侧的那本)，然后搬走这本书以及它左侧的 $k$ 本书(如果左侧不足 $k$ 本，则搬走左侧全部)和它右侧的 $k$ 本书(如果右侧不足 $k$ 本，则搬走右侧全部)。

然后是小李整理，小李的策略是找到当前书架上最重的一本书(如果有多个重量相同，则选择最右侧的那本)，然后搬走这本书以及它左侧的 $k$ 本书和右侧的 $k$ 本书(不足时的处理情况同上)。

两人轮流整理，直到所有书籍都被搬走。图书馆馆长要记录工作情况，他想知道最后两人分别搬走了哪些书籍。

输入描述

第一行为两个整数 $n(1≤n≤100000)$ 和 $k(0≤k≤n)$ ，分别表示书籍的总数量和每次搬书时向两侧扩展的书籍数量。

第二行为 $n$ 个空格隔开的整数，其中第 $i$ 个数 $a_i(1≤a_i≤1000)$ 表示第 $i$ 本书的重量。

输出描述

输出的第一行为小张搬走的书籍编号，按升序排列。

输出的第二行为小李搬走的书籍编号，按升序排列。

数据保证每人都至少搬走了一本书。

样例1

输入

10 2
3 1 4 1 5 9 2 6 5 3

输出

1 2 3 4 9 10
5 6 7 8