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

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

分析：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct p{
 4     int pos;
 5     int t;
 6 } p;
 7 p a[200100];//记录位置和时间 
 8 int b[200100];//保存所在天的下标 
 9 int cmp(const void*a,const void*b){
10     return (*(p*)a).t-(*(p*)b).t;
11 }
12 int main(void){
13     int n,m,d;
14     scanf("%d %d %d",&n,&m,&d);
15     for(int i=0;i<n;i++){
16         scanf("%d",&a[i].t);
17         a[i].pos=i;
18     }
19     qsort(a,n,sizeof(a[0]),cmp);
20     int h=0;//指向当前最早时刻 
21     int day=1;
22     b[a[0].pos]=day;//最早的记录为第一天 
23     for(int i=1;i<n;i++){
24         if(a[i].t-a[h].t>d){
25             b[a[i].pos]=b[a[h].pos];//可以在同一天 所在天的下标相同 
26             h++;
27         }
28         else{//不能在同一天 只能多开一天 
29             day++;
30             b[a[i].pos]=day;
31         }
32     }
33     printf("%d\n",day);
34     for(int i=0;i<n;i++)printf("%d ",b[i]);
35     return 0;
36 }

 

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