简答题
偏难
#13134
咖啡机 一台自动咖啡机按以下规则接单:制作一杯咖啡需要 c 秒,只有当前订单制作完成后,才能处理下一个订单。如果在制作期间,接到新订单,则做忽略处理。 有 n…
咖啡机
一台自动咖啡机按以下规则接单:制作一杯咖啡需要 c 秒,只有当前订单制作完成后,才能处理下一个订单。如果在制作期间,接到新订单,则做忽略处理。
有 n 位顾客下单,其中第 i 位顾客的下单时间为第 ti 秒,保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单?
时间限制:1000ms,内存限制:256MB
输入格式
第一行,两个整数表示 n、c;
第二行,n 个整数表示 t1、t2、t3、……、tn。
输出格式
这台咖啡机最多能完成多少杯订单。
输入样例#1
6 5 1 3 12 10 8 7
输出样例#1
3
输入样例#2
3 2 0 2 4
输出样例#2
3
输入样例#3
10 3 0 3 4 9 15 12 6 17 19 20
输出样例#3
7
数据范围:
1≤n≤100;1≤c≤1000;0≤ti≤1000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int s[1005] = {0}, t[1005]; // s表示每秒的状态
int main() {
int n, c, cnt = 0;
cin >> n >> c;
for(int i=0; i<n; i++) { //输入 n 个元素
cin >> t[i];
}
sort(t, t + n); //从小到大排序
for(int i=0; i<n; i++) {
if(s[t[i]] == 0) {
// 将t[i]开始的c秒状态置为忙
for(int j = t[i]; j<t[i]+c; j++) {
s[j] = 1;
}
cnt++;
}
}
printf("%d", cnt);
return 0;
}</pre>
这道题暂未补解析。