「Jury Compromise」 陪审团

GitHub跳转原题关系图返回列表

选 M 人使控辩总分差最小、总分和最大：以 diff=D-P 为状态维度的 01 背包（分层 DP），逐人更新并记录成员位掩码，O(N·M·range)。

OJ: roj

题目 ID: 3143

难度:省选/NOI-

标签:DP背包DP状态记录

创建: 2026-10-01 20:45

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    NN 个候选人各有控方分 pip_i、辩方分 did_i（0≤pi,di≤200\le p_i,d_i\le 20）。选出 MM 人，最小化 ∣∑p−∑d∣|\sum p - \sum d|；并列时最大化 ∑p+∑d\sum p + \sum d；再并列按题面字典序输出成员编号。

    正解

    思路

    1. 以「分差」为状态的 01 背包

    令 diff=D−P\text{diff} = D-P，目标是让 ∣diff∣|\text{diff}| 最小。直接枚举子集是 2N2^N；用 DP：

    f[j][diff]=恰好选 j 人、分差为 diff 时的最大总分和(P+D)f[j][\text{diff}] = \text{恰好选 } j \text{ 人、分差为 diff 时的最大总分和}(P+D)

    j=1..Mj=1..M 分层，每人是 01 物品（Δdiff=di−pi\Delta\text{diff}=d_i-p_i，Δsum=di+pi\Delta\text{sum}=d_i+p_i）。转移从 f[j−1]f[j-1] 来，jj 从大到小滚动防止同人选两次。

    2. 记录成员集合

    状态里额外保存成员位掩码（N≤200N\le 200 时用 Python 整数当位集）。并列时按题面字典序规则决出：先按 ∣di−pi∣|d_i-p_i| 降序处理候选人（分歧大的先定下来），保证位掩码并列比较稳定。

    3. 答案提取

    在 f[M]f[M] 里扫 ∣diff∣|\text{diff}| 最小者（并列取总分最大），按位掩码还原编号序列输出。

    代码

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 陪审团：按差值做 01 背包，层内按插入顺序扫描，位掩码记录成员集合。
#include <cstdio>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cstdlib>

typedef long long ll;

const int MW = 4; // n ≤ 200，成员掩码需要 4 个 64 位字

struct Mask {
    unsigned long long w[MW];
};

struct Entry {
    ll diff;  // D - P
    ll value; // P + D 之和
    Mask mask;
};

// 一层：entries 保持「插入顺序」（与 Python dict 的迭代顺序一致），idx 提供按键查找
struct Layer {
    std::vector<Entry> entries;
    std::map<ll, int> idx;
};

std::vector<ll> nums;
size_t npos = 0;

// 读入全部整数：先按行去掉 `//` 注释，再逐行分词
void read_all() {
    std::vector<char> raw;
    int ch;
    while ((ch = getchar()) != EOF) raw.push_back((char)ch);

    std::string text(raw.begin(), raw.end());
    size_t start = 0;
    while (start <= text.size()) {
        size_t nl = text.find('\n', start);
        std::string line = (nl == std::string::npos) ? text.substr(start) : text.substr(start, nl - start);
        size_t cm = line.find("//");
        if (cm != std::string::npos) line = line.substr(0, cm);
        const char* p = line.c_str();
        while (*p) {
            char* end;
            long long v = strtoll(p, &end, 10);
            if (end == p) break;
            nums.push_back(v);
            p = end;
        }
        if (nl == std::string::npos) break;
        start = nl + 1;
    }
    npos = 0;
}

int main() {
    read_all();
    std::vector<std::string> blocks;
    ll case_id = 0;

    while (npos + 2 <= nums.size()) {
        ll n = nums[npos++];
        ll m = nums[npos++];
        if (n == 0 && m == 0) break;
        case_id++;

        std::vector<ll> p(n), d(n);
        for (ll i = 0; i < n; i++) {
            p[i] = nums[npos++];
            d[i] = nums[npos++];
        }

        // 并列最优时打印哪一组由扫描顺序决定，按 |d-p| 降序先处理分歧大的候选人
        std::vector<ll> order(n);
        for (ll i = 0; i < n; i++) order[i] = i;
        for (ll i = 0; i < n; i++) { // 按 |d-p| 降序做稳定排序
            for (ll j = i + 1; j < n; j++) {
                ll a = d[order[i]] - p[order[i]];
                ll b = d[order[j]] - p[order[j]];
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                if (b > a) {
                    ll t = order[i]; order[i] = order[j]; order[j] = t;
                }
            }
        }

        std::vector<Layer> layers(m + 1);
        for (ll t = 0; t < n; t++) {
            ll i = order[t];
            ll delta = d[i] - p[i];
            ll total = d[i] + p[i];
            Mask bit;
            for (int w = 0; w < MW; w++) bit.w[w] = 0;
            bit.w[i >> 6] |= 1ULL << (i & 63);

            // j 从大到小：本层只读上一层，保证同一个人不会被选两次
            for (ll j = m; j >= 2; j--) {
                Layer& layer = layers[j];
                Layer& prev = layers[j - 1];
                for (size_t q = 0; q < prev.entries.size(); q++) {
                    ll nd = prev.entries[q].diff + delta;
                    ll nv = prev.entries[q].value + total;
                    std::map<ll, int>::iterator it = layer.idx.find(nd);
                    if (it == layer.idx.end()) {
                        Entry e;
                        e.diff = nd;
                        e.value = nv;
                        e.mask = prev.entries[q].mask;
                        for (int w = 0; w < MW; w++) e.mask.w[w] |= bit.w[w];
                        layer.idx[nd] = (int)layer.entries.size();
                        layer.entries.push_back(e);
                    } else if (nv > layer.entries[it->second].value) {
                        layer.entries[it->second].value = nv;
                        layer.entries[it->second].mask = prev.entries[q].mask;
                        for (int w = 0; w < MW; w++) {
                            layer.entries[it->second].mask.w[w] |= bit.w[w];
                        }
                    }
                }
            }
            // 单人状态最后写：否则它会被上面的循环再叠一个人，变成两人一组
            {
                Layer& layer = layers[1];
                std::map<ll, int>::iterator it = layer.idx.find(delta);
                if (it == layer.idx.end()) {
                    Entry e;
                    e.diff = delta;
                    e.value = total;
                    e.mask = bit;
                    layer.idx[delta] = (int)layer.entries.size();
                    layer.entries.push_back(e);
                } else if (total > layer.entries[it->second].value) {
                    layer.entries[it->second].value = total;
                    layer.entries[it->second].mask = bit;
                }
            }
        }

        // 目标：|D-P| 最小，并列时 P+D 最大；min 取第一个最小元（插入顺序）
        Layer& last = layers[m];
        ll bestpos = 0;
        for (size_t q = 0; q < last.entries.size(); q++) {
            ll t = last.entries[q].diff;
            if (t < 0) t = -t;
            ll bt = last.entries[bestpos].diff;
            if (bt < 0) bt = -bt;
            if (t < bt || (t == bt && last.entries[q].value > last.entries[bestpos].value)) {
                bestpos = q;
            }
        }

        Mask chosen = last.entries[bestpos].mask;
        ll total = last.entries[bestpos].value;
        ll prosecution = 0;
        std::vector<ll> pick;
        for (ll i = 0; i < n; i++) {
            if ((chosen.w[i >> 6] >> (i & 63)) & 1ULL) {
                pick.push_back(i + 1);
                prosecution += p[i];
            }
        }

        char buf[256];
        std::string blk;
        snprintf(buf, sizeof(buf), "Jury #%lld\n", case_id);
        blk += buf;
        snprintf(buf, sizeof(buf),
                 "Best jury has value %lld for prosecution and value %lld for defence:\n",
                 prosecution, total - prosecution);
        blk += buf;
        for (size_t i = 0; i < pick.size(); i++) {
            snprintf(buf, sizeof(buf), " %lld", pick[i]);
            blk += buf;
        }
        blocks.push_back(blk);
    }

    for (size_t i = 0; i < blocks.size(); i++) {
        if (i) printf("\n\n");
        printf("%s", blocks[i].c_str());
    }
    printf("\n");
    return 0;
}
    python
    #!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:27
# update_at: 2026-10-01 20:27

import sys
from collections.abc import Iterator


def read_ints(raw: str) -> Iterator[int]:
    """切出全部整数：官方数据每行尾部带 `//` 说明，先按行去掉注释再分词。"""
    for line in raw.splitlines():
        yield from map(int, line.split("//")[0].split())


def build(p: list[int], d: list[int], m: int) -> list[dict[int, tuple[int, int]]]:
    """逐人做 01 背包：layers[j][diff] = (总分和 P+D, 成员位掩码)，diff = D-P。"""
    # 并列最优时打印哪一组由扫描顺序决定，按 |d-p| 降序先处理分歧大的候选人
    order = sorted(range(len(p)), key=lambda i: -abs(d[i] - p[i]))
    layers: list[dict[int, tuple[int, int]]] = [{}]
    for i in order:
        delta, total, bit = d[i] - p[i], d[i] + p[i], 1 << i
        if len(layers) <= m:
            layers.append({})
        # j 从大到小：本层只读上一层，保证同一个人不会被选两次
        for j in range(len(layers) - 1, 1, -1):
            layer, prev = layers[j], layers[j - 1]
            for diff, (value, mask) in prev.items():
                nxt = layer.get(diff + delta)
                if nxt is None or value + total > nxt[0]:
                    layer[diff + delta] = (value + total, mask | bit)
        # 单人状态最后写：否则它会被上面的循环再叠一个人，变成两人一组
        layer = layers[1]
        nxt = layer.get(delta)
        if nxt is None or total > nxt[0]:
            layer[delta] = (total, bit)
    return layers


def solve() -> None:
    data = read_ints(sys.stdin.buffer.read().decode())
    blocks: list[str] = []
    case = 0

    while True:
        n, m = next(data), next(data)
        if n == 0 and m == 0:
            break
        case += 1

        scores = [next(data) for _ in range(2 * n)]  # 每人两个分值，按控方、辩方交替给出
        p, d = scores[::2], scores[1::2]

        layers = build(p, d, m)
        # 目标：|D-P| 最小，并列时 P+D 最大；diff 就是 D-P，故按 (|diff|, -总分和) 取最优
        best = min(layers[m], key=lambda t: (abs(t), -layers[m][t][0]))
        total, mask = layers[m][best]
        chosen = [i + 1 for i in range(n) if mask >> i & 1]
        prosecution = sum(p[i - 1] for i in chosen)

        blocks.append(
            f"Jury #{case}\n"
            f"Best jury has value {prosecution} for prosecution "
            f"and value {total - prosecution} for defence:\n"
            + " " + " ".join(map(str, chosen))
        )

    print("\n\n".join(blocks))


if __name__ == "__main__":
    solve()

    复杂度

    • 时间复杂度：O(N⋅M⋅R)O(N \cdot M \cdot R)，RR 为 diff 值域（≤40M\le 40M）。
    • 空间复杂度：O(M⋅R)O(M \cdot R)。

    总结

    • 「选 k 个使差值最小、和最大」= 以差值为费用、和为价值的双维度 01 背包。
    • 并列决策需要稳定的打破顺序：按 ∣di−pi∣|d_i-p_i| 降序处理 + 位掩码比较是简洁做法。
    • Python 的任意精度整数天然适合做 200 位以内的成员位集。