A. Coffee Break(思维题，类似于邻接表的head数组用法)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题：https://codeforces.com/gym/101911/problem/A

题意：每天工作m分钟，每次喝coffee得间隔d分钟，然后给出n个数，每个数表示想在一天中的a[i]的时刻喝coffe，问最少喝完的天数

分析：先对数组升序排，若满足间隔的d就向前一个建立联系；

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+;
int ans[M],head[M];
pair<int,int >a[M];
int main(){
int n,m,d;
scanf("%d%d%d",&n,&m,&d);
for(int i=,x;i<n;i++)
scanf("%d",&x),a[i].first=x,a[i].second=i;
sort(a,a+n);
int j=;
head[]=-;
for(int i=;i<n;i++){
if(a[i].first-a[j].first>d)
head[i]=j,j++;
else
head[i]=j-;
}
int tot=; for(int i=n-;i>=;i--){
if(!ans[a[i].second]){
tot++;
for(j=head[i];~j;j=head[j])
ans[a[j].second]=tot;
ans[a[i].second]=tot;
}
}
printf("%d\n",tot);
for(int i=;i<n;i++)
printf("%d ",ans[i]);
return ;
}