模拟 二分
- 题面
- 题意
- 分析
- 代码
题面 【codeforces Convention】Cows from all over the world are arriving at the local airport to attend the convention and eat grass. Specifically, there are N cows arriving at the airport (1≤N≤105) and cow i arrives at time ti (0≤ti≤109). Farmer John has arranged M (1≤M≤105) buses to transport the cows from the airport. Each bus can hold up to C cows in it (1≤C≤N). Farmer John is waiting with the buses at the airport and would like to assign the arriving cows to the buses. A bus can leave at the time when the last cow on it arrives. Farmer John wants to be a good host and so does not want to keep the arriving cows waiting at the airport too long. What is the smallest possible value of the maximum waiting time of any one arriving cow if Farmer John coordinates his buses optimally? A cow’s waiting time is the difference between her arrival time and the departure of her assigned bus.
It is guaranteed that MC≥N.
Input
The first line contains three space separated integers N, M, and C. The next line contains N space separated integers representing the arrival time of each cow.
Output
Please write one line containing the optimal minimum maximum waiting time for any one arriving cow.
input
6 3 2
1 1 10 14 4 3
output
4
题意 就是N牛M车 一车最多载C牛
每头牛有一个到达的时间，这辆车出发的时间-上这辆车最早到那个牛的时间就是等待时间，问怎么分配使得所有车的最大等待时间最小。
分析 一开始想着的是模拟，觉得一头牛要么上上一辆车，要么再上一辆新车。后来wa了，结束后dl说是二分。自己试试果然如此。
使用二分猜答案，再根据答案模拟上车过程，如果车辆小于M则不是最优，大于M则不可能来调整区间。
代码
#include
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n,m,c;
ll t[100005];
bool cmp(ll x){
int i,cnt=1,first;
for(first=i=0;
ix) { first=i;
cnt++;
continue;
}
if(i-first+1==c && i!=n-1){ first=i+1;
cnt++;
continue;
}
}
//printf("cnt %d\n",cnt);
if(cnt>m) return false;
//过小
return true;
//可能过大
}
int main(){
int i;
scanf("%d%d%d",&n,&m,&c);
for(i=0;
i 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络