Gym-101911A Coffee Break

题目：https://vjudge.net/problem/Gym-101911A

题意：n、m、d分别表示Mo想休息的次数、每天最大的工作时长以及两次休息的最小间隔,ai为Mo想休息的时刻，求休息n次所需的最少天数，以及按所给顺序每个时刻所在的天的下标。

分析：贪心。定义一个结构体a存时间和位置，再开一个数组用来保存所在的天的下标。按照时间顺序排序，不妨让最早的时刻在第一天，并设置一个索引指向当前的最早时刻，如果当前时刻与指向的最早时刻满足时间差大于d,则记为同一天；否则后面的时间更不可能满足，只能多开一天。

  #include <stdio.h>
  #include <stdlib.h>
  typedef struct p{
      int pos;
      int t;
  } p;
  p a[200100];//记录位置和时间 
  int b[200100];//保存所在天的下标 
  int cmp(const void*a,const void*b){
     return (*(p*)a).t-(*(p*)b).t;
 }
 int main(void){
     int n,m,d;
     scanf("%d %d %d",&n,&m,&d);
     for(int i=0;i<n;i++){
         scanf("%d",&a[i].t);
         a[i].pos=i;
     }
     qsort(a,n,sizeof(a[0]),cmp);
     int h=0;//指向当前最早时刻 
     int day=1;
     b[a[0].pos]=day;//最早的记录为第一天 
     for(int i=1;i<n;i++){
         if(a[i].t-a[h].t>d){
             b[a[i].pos]=b[a[h].pos];//可以在同一天 所在天的下标相同 
             h++;
         }
         else{//不能在同一天 只能多开一天 
             day++;
             b[a[i].pos]=day;
         }
    }
     printf("%d
",day);
     for(int i=0;i<n;i++)printf("%d ",b[i]);
    return 0;
 }