A22929. 咖啡机
填空题
较难
知识点
题目描述
咖啡机
题目描述
一台自动咖啡机按以下规则接单：制作一杯咖啡需要 c 秒，只有当前订单制作完成后，才能处理下一个订单。如果在制作期间，接到新订单，则做忽略处理。
有 n 位顾客下单，其中第 i 位顾客的下单时间为第 ti 秒，保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单？
输入格式
第一行，两个整数表示 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参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,a[N];
bool cnt[N];
signed main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(!cnt[a[i]])
{
if(a[i] != a[i + 1]) ans++;
for(int j = a[i]; j <= 1e6; j += a[i]) cnt[j] = true;
}
}
printf("%d",ans);
}
上一题
下一题