题解：P14496 [NCPC 2025] Bohemian Bookshelf

A1cZheng · 2025-11-29 12:11:43 · 题解

思路：

首先将书籍按高度从高到低排序，保证“不增顺序”。

然后遍历所有书籍，将其中一本作为直立书籍的“代表”。再尝试剩余书籍能否加入直立堆。

对剩下的书进行堆叠，累加厚度，超过书架高度就停下。

然后检查直立书籍的总厚度加上堆叠书籍的总厚度是否小于等于书架宽度，确保所有书籍可以同时放在书架上。

遍历所有书籍，检查未加入堆叠的书籍能否作为直立书籍。若存在不符合条件的书籍，则放弃此方案。

最后输出合理方案，如果没有合理方案，那么最终会退出循环，然后输出impossible。

:::info[Code]

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e3 + 5;
int n, h0, w0;
int h[maxn], t[maxn], id[maxn];
int stk[maxn], tot;
bool cmp (int a, int b) {
    return h[a] > h[b];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> h0 >> w0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> t[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    int sum_t = 0;
    for (int i = 1; i <= n; i++) {
        sum_t += t[i];
    }
    for (int i = 1; i <= n; i++) {
        int now = id[i];
        if (h[now] > w0) { 
            continue; 
        }
        int s_t = 0;
        tot = 0;
        for (int j = i; j <= n; j++) {
            int col = id[j];
            if (s_t + t[col] > h0) { 
                break; 
            }
            s_t += t[col];
            stk[tot++] = col;
            int ut = sum_t - s_t;
            if (tot < n && ut + h[now] <= w0) {
                bool flag = 1;
                for (int k = 1; k <= n; k++) {
                    int tmp = id[k];
                    bool flag2 = 0;
                    for (int l = 0; l < tot; l++) {
                        if (stk[l] == tmp) { 
                            flag2 = 1; 
                            break; 
                        }
                    }
                    if (!flag2 && h[tmp] > h0) {  
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    cout << "upright";
                    for (int k = 1; k <= n; k++) {
                        int tmp = id[k];
                        if (tmp != now && find(stk, stk + tot, tmp) == stk + tot) { 
                            cout << " " << tmp; 
                        }
                    }
                    cout << "\n";
                    cout << "stacked";
                    for (int k = 0; k < tot; k++) { 
                        cout << " " << stk[k]; 
                    }
                    return 0;
                }
            }
        }
    }
    cout << "impossible";
    return 0;
}

:::