打卡信奥刷题（2807）用C++实现信奥题 B4093 [CSP-X2021 山东] 发送快递

题目摘要：B4093 [CSP-X2021 山东] 发送快递本题要求将n本不同重量的书打包成快递包裹，每个包裹不超过m公斤。输入包括书的数量n、最大重量m、各书重量、必须打包的s组书（s=0时无限制）。输出最少快递件数。样例1展示了3件快递的解法，样例2展示了4件快递的解法。数据范围：n≤23，ai≤100，s≤15。解题思路包括处理必须打包的组，剩余书按重量排序，使用DFS搜索最优组合。C++

rogeliu

757人浏览 · 2026-02-07 08:40:01

rogeliu · 2026-02-07 08:40:01 发布

B4093 [CSP-X2021 山东] 发送快递

题目背景

原题为错题，不可做。数据范围修改如下，请以题目背景中的为准：

【数据范围和限制】

对于 $40%40\%$ 的数据， $\leq n \leq 23$ ， $\leq a_i \leq 100$ ， $s = 0$ ， $m$ 的值保证有解。

对于 $100%100\%$ 的数据， $\leq n \leq 23$ ， $\leq a_i \leq 100$ ， $\leq s \leq 15$ ， $m$ 的值保证有解。

为了防止无意义的钻牛角尖的 hack，本题认为 $m$ 不超过 $2^{31}-1$ 。

题目描述

小华有 $n$ 本不同的书（编号为 $1,2,3,…,n1,2,3,\dots,n$ ），重量分别是 $a1,a2,…,ana_1,a_2,\dots,a_n$ 公斤（重量可以相同）。他想把这些书以快递的方式发给自己的好朋友，要求每个包裹的重量不能超过 $m$ 公斤（可以等于 $m$ 公斤），并且小华想把其中一些书（一组书，用书的编号给出来）放在一个包裹里，应该如何打包才能使得快递件数最少。

输入格式

第一行，包含两个整数 $n, m$ ，之间用一个空格隔开，分别表示书的数量和快递包裹的最大重量。

第二行 $n$ 个整数 $a_i$ ，表示 $n$ 本书的重量，每两个整数之间用一个空格隔开。

第三行一个整数 $s$ ，表示一共有 $s$ 组书（每组书需要打包在一起）。如果 $s = 0$ ，则无此限制。数据保证每组书的重量不超过 $m$ 。

第四行开始共 $s$ 行，每行若干个整数，表示必须放在一个包裹里的书的编号，每两个整数之间用一个空格隔开。

输出格式

输出文件一行，一个整数，即快递最少件数。

输入输出样例 #1

输入 #1

5 10
8 4 8 2 5
0

输出 #1

输入输出样例 #2

输入 #2

10 80
49 11 44 18 28 24 19 10 27 29
2
1 5
4 8 2

输出 #2

说明/提示

【输入输出样例 1 说明】

第 $1$ 本和第 $4$ 本打包，重量是 $10$ 公斤。第 $2$ 本和第 $5$ 本打包，重量是 $9$ 公斤。第 $3$ 本单独打包，重量是 $8$ 公斤。所以一共 $3$ 件快递。

【输入输出样例 2 说明】

第 $1$ 本和第 $5$ 本打包，第 $2$ 本、第 $4$ 本、第 $8$ 本和第 $10$ 本打包，第 $3$ 本和第 $7$ 本打包，第 $6$ 本和第 $9$ 本打包。所以一共 $4$ 件快递。

【数据范围和限制】

对于 $40%40\%$ 的数据， $\leq n \leq 10^5$ ， $\leq a_i \leq 100$ ， $s = 0$ ， $m$ 的值保证有解。

对于 $100%100\%$ 的数据， $\leq n \leq 10^5$ ， $\leq a_i \leq 100$ ， $\leq s \leq 100$ ， $m$ 的值保证有解。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,ans=54,c[55],b[55],a[55],r,lst,p,k;
vector<int> G[55];
bool vis[55];
void build(int now){
    vis[now]=1;
    a[p]+=b[now];
    for(int i:G[now]){
        if(!vis[i]) build(i);
    }
}
bool cmp(int a,int b){
    return a>b;
}
void dfs(int now,int val){
    if(val>=ans) return;
    if(now==p+1){
        ans=val;
        return ;
    }
    for(int i=1;i<=k;i++){
        if(c[i]+a[now]<=m){
            c[i]+=a[now];
            dfs(now+1,val);
            c[i]-=a[now];
        }
    }
    k++;
    c[k]+=a[now];
    dfs(now+1,val+1);
    c[k]-=a[now];
    k--;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    cin>>s;
    for(int i=1;i<=s;i++){
        cin>>lst;
        while(cin>>r){
            G[lst].push_back(r);
            G[r].push_back(lst);
            lst=r;
            if(cin.get()=='\n') break;
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) p++,build(i);
    sort(a+1,a+1+p,cmp);
    dfs(1,0);
    cout<<ans;
    return 0;
}