PEEK125 皇后游戏

题目链接

PEEK125 皇后游戏

题目描述

皇后有 位大臣，每位大臣左右手分别写着正整数 。大臣们需要排成一队。

第 位大臣获得的奖金 由他前面大臣的奖金 、他前面大臣（包括自己）左手数字之和 以及他自己右手数字 决定。

递推公式为：

，其中 。

目标是找到一个大臣的排列顺序，使得所有大臣中获得奖金的最大值 尽可能小。

解题思路

这是一个典型的排序贪心问题，目标是最小化最大奖金。问题的核心是找到一个最优的排序准则。

这个奖金的递推公式与一个经典的调度问题模型——双机流水调度（Johnson's Algorithm）——完全一致。

我们可以将问题类比为在两条流水线上加工 个工件：

  • 每个大臣看作一个工件。
  • 是工件 在第一台机器上的加工时间。
  • 是工件 在第二台机器上的加工时间。

工件必须先在第一台机器加工，再在第二台机器加工。

  • (我们记作 ) 就代表前 个工件在第一台机器上加工完成的时刻。
  • 代表前 个工件在第二台机器上加工完成的时刻。

工件 要在第二台机器上开始加工，必须满足两个条件：

  1. 它自身在第一台机器上的加工已经完成（时刻 ）。
  2. 第二台机器已经完成了上一个工件 的加工（时刻 ）。

所以，工件 在第二台机器上的开始加工时刻是 。

加工耗时为 ，因此完成时刻就是 ，这与题目的奖金公式完全相同。

我们要求解的是 ，即最小化所有工件在第二台机器上完成时间的最大值。在调度问题中，这等价于最小化最大完工时间（Makespan）。

Johnson's Algorithm 提供了解决此问题的最优排序策略：

  1. 将所有大臣（工件）分为两组：
    • 组 U： 的大臣。
    • 组 V： 的大臣。
  2. 对组 U 中的大臣，按照 的值从小到大排序。
  3. 对组 V 中的大臣，按照 的值从大到小排序。
  4. 最终的最优队列顺序是：排好序的组 U 接着排好序的组 V。

这个排序准则可以被严格证明，其核心思想是优先处理在第一台机器上耗时短的工件，并把在第二台机器上耗时长的工件安排到队尾，以减少第二台机器的空闲等待时间。

算法步骤：

  1. 读入所有大臣的数据。
  2. 根据 Johnson's Algorithm 的规则对大臣进行排序。可以直接实现一个自定义比较函数来完成排序。
  3. 排序后，遍历大臣队列，按照递推公式计算每个大臣的奖金。
    • 维护一个变量 sum_a 记录 的前缀和。
    • 维护一个变量 prev_c 记录前一位大臣的奖金。
    • 维护一个变量 max_c 记录到目前为止的最大奖金。
  4. 遍历结束后，max_c 就是所求的答案。
  5. 由于奖金和 的前缀和可能会超过普通 int 的范围，需要使用 long long (C++) 或 long (Java) 来存储。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Minister {
    int a, b;
};

// Johnson's Algorithm 排序准则
bool compareMinisters(const Minister& m1, const Minister& m2) {
    if (m1.a < m1.b && m2.a >= m2.b) {
        return true;
    }
    if (m1.a >= m1.b && m2.a < m2.b) {
        return false;
    }
    if (m1.a < m1.b) { // Both in group U (a < b)
        return m1.a < m2.a;
    } else { // Both in group V (a >= b)
        return m1.b > m2.b;
    }
}

void solve() {
    int n;
    cin >> n;
    vector<Minister> ministers(n);
    for (int i = 0; i < n; ++i) {
        cin >> ministers[i].a >> ministers[i].b;
    }

    sort(ministers.begin(), ministers.end(), compareMinisters);

    long long sum_a = 0;
    long long prev_c = 0;
    long long max_c = 0;

    for (int i = 0; i < n; ++i) {
        sum_a += ministers[i].a;
        long long current_c = max(prev_c, sum_a) + ministers[i].b;
        max_c = max(max_c, current_c);
        prev_c = current_c;
    }

    cout << max_c << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

class Minister {
    int a, b;

    public Minister(int a, int b) {
        this.a = a;
        this.b = b;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        ArrayList<Minister> ministers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ministers.add(new Minister(sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(ministers, (m1, m2) -> {
            if (m1.a < m1.b && m2.a >= m2.b) {
                return -1;
            }
            if (m1.a >= m1.b && m2.a < m2.b) {
                return 1;
            }
            if (m1.a < m1.b) { // Both in group U (a < b)
                return Integer.compare(m1.a, m2.a);
            } else { // Both in group V (a >= b)
                return Integer.compare(m2.b, m1.b);
            }
        });

        long sum_a = 0;
        long prev_c = 0;
        long max_c = 0;

        for (int i = 0; i < n; i++) {
            sum_a += ministers.get(i).a;
            long current_c = Math.max(prev_c, sum_a) + ministers.get(i).b;
            max_c = Math.max(max_c, current_c);
            prev_c = current_c;
        }
        System.out.println(max_c);
    }
}

import sys

def solve():
    n = int(input())
    ministers = []
    for _ in range(n):
        a, b = map(int, input().split())
        ministers.append({'a': a, 'b': b})
    
    # 根据 Johnson's Algorithm 排序
    group_u = sorted([m for m in ministers if m['a'] < m['b']], key=lambda x: x['a'])
    group_v = sorted([m for m in ministers if m['a'] >= m['b']], key=lambda x: x['b'], reverse=True)
    
    sorted_ministers = group_u + group_v
    
    sum_a = 0
    prev_c = 0
    max_c = 0
    
    for m in sorted_ministers:
        sum_a += m['a']
        current_c = max(prev_c, sum_a) + m['b']
        max_c = max(max_c, current_c)
        prev_c = current_c
        
    print(max_c)

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 (Johnson's Algorithm)。
  • 时间复杂度：主要开销在于排序，所以时间复杂度为 。排序后计算奖金的循环是 。对于 组数据，总时间复杂度为 。
  • 空间复杂度：，用于存储所有大臣的信息。