AT2337

上杉越 · 2022-02-13 14:10:11 · 题解

这题为啥是黄题

传送门

题目描述：

有 N 位乘客，第 i 位将在时刻 Ti 抵达机场。

你需要发出一些公交，将所有乘客从机场送到城市。如果一班公交在时刻 t 出发，那么所有满足 Ti ≤ t ≤ Ti + K 的乘客 i 可以坐上这一班公交。但是一班公交只能坐 c 人。

你可以在任意时刻发出公交（可以同时发车）求最少发车次数。

算法：贪心

思路：

将每一个人的上车时间进行排序，时间早的在前。设 time 为发车时间， time 越晚越好，因为这样可以尽可能的使公交的乘客更多。

当公交的乘客达到上限或这个公交无法满足这位乘客时，增加一辆公交。

Coding:

#include<bits/stdc++.h>//懒人头文件
using namespace std;
int n,k,c,t[100086];
int main(){
    cin>>n>>c>>k;
    for(int i=1;i<=n;i++)cin>>t[i];
    sort(t+1,t+n+1);
    int time=t[1]+k,sum=1,ans=1;
    /*time为发车时间，sum为此时公交上的人数，ans为已发车辆。*/
    for(int i=2;i<=n;i++){
        if(sum==c){//当公交坐满时
            ans++,sum=1;//需要发出的车加一，车上人数变为一。
            time=t[i]+k;//更改发车时间
        }
        else{
            if(t[i]<=time&&time<=t[i]+k)sum++;//公交人数加一
            else{
                ans++,sum=1;//同上
                time=t[i]+k;
            }
        }
    }
    cout<<ans;
    return 0;
}

点个赞再走呗！