题解：AtCoder AT_awc0088_b Bus Tour Group Division-程序员充电站

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

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

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

【题目来源】

AtCoder：B - Bus Tour Group Division

【题目描述】

Takahashi is a tour conductor at a travel agency. For the upcoming bus tour,N NNparticipants have signed up, and each participant has a preferred departure time.

The preferred departure time of each participanti ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)isT i T_iTi. According to the travel agency’s policy, to operate tours efficiently, participants with similar preferred departure times are grouped together on the same bus. Specifically, for any two participantsi , j i, ji,jon the same bus, the absolute difference of their preferred departure times∣ T i − T j ∣ |T_i - T_j|∣Ti−Tj∣must be at mostK KK. There is no upper limit on the number of people that can ride on a single bus.

Takahashi wants to assign every participant to exactly one bus and minimize the number of buses required.

Find the minimum number of buses needed to assign all participants to buses.

高桥是一家旅行社的导游。在即将到来的巴士旅行中，有N NN名参与者报名，每位参与者都有一个偏好的出发时间。

每位参与者i ii（1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N）的偏好出发时间是T i T_iTi。根据旅行社的政策，为了高效运营旅行，偏好出发时间相近的参与者会被分到同一辆巴士上。具体来说，对于同一辆巴士上的任意两位参与者i , j i, ji,j，他们偏好出发时间的绝对差∣ T i − T j ∣ |T_i - T_j|∣Ti−Tj∣必须不超过K KK。一辆巴士可以乘坐的人数没有上限。

高桥希望将每位参与者分配到恰好一辆巴士上，并最小化所需巴士的数量。

求将所有参与者分配到巴士上所需的最少巴士数量。

【输入】

N NNK KK
T 1 T_1T1T 2 T_2T2… \ldots…T N T_NTN

The first line containsN NN, the number of participants, andK KK, the maximum allowed absolute difference in preferred departure times for participants on the same bus, separated by a space.
The second line contains the preferred departure timesT 1 , T 2 , … , T N T_1, T_2, \ldots, T_NT1,T2,…,TNof each participant, separated by spaces.

【输出】

Print the minimum number of buses needed to assign all participants to buses, on a single line.

【输入样例】

5 3 1 5 3 9 12

【输出样例】

【算法标签】

#其他排序

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义数组最大容量constintN=200005;// 全局变量声明intn,k;// n: 元素个数, k: 允许的最大差值inta[N];// 存储所有元素的数组// 主函数入口intmain(){// 读取元素个数n和差值限制kcin>>n>>k;// 循环读取n个元素到数组中for(inti=1;i<=n;i++)cin>>a[i];// 对数组进行升序排序sort(a+1,a+n+1);// 贪心算法：计算最少需要多少个分组intans=1;// 至少有一个分组intlast=a[1];// 记录当前分组的第一个元素// 从第二个元素开始遍历for(inti=2;i<=n;i++){// 如果当前元素与分组起始元素的差值不超过k，则归入同一组if(a[i]-last<=k)continue;else{// 否则开启新分组，更新分组起始元素ans++;last=a[i];}}// 输出最少分组数量cout<<ans<<endl;return0;}