当前位置：首页 > news >正文

题解：AtCoder AT_awc0005_d Splitting Delivery Packages

news 2026/4/29 23:43:34

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Splitting Delivery Packages

【题目描述】

Takahashi is in charge of delivery planning at a shipping company.
高桥负责一家货运公司的送货路线规划工作。

Today, he needs to create a plan to deliverN NNpackages usingK KKtrucks.
今天，他需要制定一个使用K KK辆卡车运送N NN个包裹的计划。

Each package is numbered from1 11toN NN, and the weight of packagei iiisA i A_iAi.
每个包裹编号从1 11到N NN，且包裹i ii的重量为A i A_iAi。

To improve delivery efficiency, he decided to arrange the packages1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nin this order and divide them intoK KKcontiguous segments, each containing at least1 11package, and assign the packages in each segment to one truck. Every package belongs to exactly one segment, and there is a one-to-one correspondence between theK KKsegments and theK KKtrucks.
为了提高送货效率，他决定将包裹1 , 2 , … , N 1, 2, …, N1,2,…,N按此顺序排列，并将其分割为K KK个连续段（每段至少包含1 11个包裹），然后将每段中的包裹分配给一辆卡车。每个包裹恰好属于一个段，并且K KK个段与K KK辆卡车之间存在一一对应关系。

For each truck, the sum of the weights of the packages assigned to that truck is called theloadof that truck.
对于每辆卡车，分配给该卡车的包裹重量之和称为该卡车的载重。

Takahashi wants to maximize the smallest load among theK KKtrucks.
高桥希望最大化K KK辆卡车中最小的载重。

Considering all possible ways to divide the packages, find the maximum possible value of “the minimum load among theK KKtrucks.”
考虑所有可能的分割包裹方式，求"K KK辆卡车中最小的载重"的最大可能值。

【输入】

N NNK KK
A 1 A_1A1A 2 A_2A2… \ldots…A N A_NAN

The first line contains an integerN NNrepresenting the number of packages and an integerK KKrepresenting the number of trucks, separated by a space.
The second line containsN NNintegersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting the weight of each package, separated by spaces.

【输出】

Print in one line the maximum possible value of the minimum load among theK KKtrucks when the packages are divided optimally.

【输入样例】

5 2 1 2 3 4 5

【输出样例】

【解题思路】

【算法标签】

#整数二分#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;intn,k;// n: 数组长度，k: 所需分段数inta[N];// 数组// 检查是否能够将数组分割为至少k段，使得每段和至少为xboolcheck(intx){intsum=0,ans=0;// sum: 当前段的和，ans: 已分割的段数for(inti=1;i<=n;i++){if(sum+a[i]>=x)// 如果将当前元素加入会使段和达到x{ans++;// 段数加1sum=0;// 重置当前段和}else{sum+=a[i];// 将当前元素加入当前段}}returnans>=k;// 返回是否能分割出至少k段}signedmain(){cin>>n>>k;// 读入数组长度和所需段数for(inti=1;i<=n;i++){cin>>a[i];// 读入数组}intl=0,r=1e18;// 二分查找范围while(l<r)// 二分查找{intmid=(l+r+1)/2;// 计算中点if(check(mid))// 如果mid可行{l=mid;// 尝试更大的值}else{r=mid-1;// 尝试更小的值}}cout<<l<<endl;// 输出最大的满足条件的xreturn0;}