CF1041C Coffee Break（二分+贪心+set）

描述

Recently Monocarp got a job. His working day lasts exactly mm minutes. During work, Monocarp wants to drink coffee at certain moments: there are nn minutes a1,a2,…,ana1,a2,…,an, when he is able and willing to take a coffee break (for the sake of simplicity let’s consider that each coffee break lasts exactly one minute).
However, Monocarp’s boss doesn’t like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute aiai, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least dd minutes pass between any two coffee breaks. Monocarp also wants to take these nn coffee breaks in a minimum possible number of working days (he doesn’t count days when he is not at work, and he doesn’t take coffee breaks on such days). Take into account that more than dd minutes pass between the end of any working day and the start of the following working day.
For each of the nn given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent.

输入

The first line contains three integers nn, mm, dd (1≤n≤2⋅105,n≤m≤109,1≤d≤m)(1≤n≤2⋅105,n≤m≤109,1≤d≤m) — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.
The second line contains nn distinct integers a1,a2,…,ana1,a2,…,an (1≤ai≤m)(1≤ai≤m), where aiai is some minute when Monocarp wants to have a coffee break.

输出

Input

4 5 3
3 5 1 2

Output

3
3 1 1 2

Input

10 10 1
10 5 7 4 6 3 2 1 9 8

Output

2
2 1 1 2 2 1 2 1 1 2

题解：我们选取时刻的时候，贪心思想尽量每次把最小的安排进一天中，如果找不到的话就在开启新的一天并重复以上操作。

对于频繁的查找和删除某一个数，那肯定是用set了；
这样的话时间复杂度为O(nlog(n))了；

代码

#pragma GCC optimize(3,"Ofast","inline")  
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <algorithm>
#define MaxN  0x3f3f3f3f3f
#define MinN  0xc0c0c0c0c0
using namespace std;
struct wazxy{int i,num;friend bool operator < (const wazxy & a,const wazxy & b){   //当我们set容器放入结构体时，需要重载一下运算符return a.num<b.num;    //自定义排序规则}
};
set<wazxy> a;
wazxy x;
int position[200010];   //建立一个数组储存他是第几次操作；
int main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){scanf("%d",&x.num);x.i=i;a.insert(x);   //将内容放进set容器；}int xx=(*a.begin()).num,cnt=1;  //贪心  找最小的那个；position[(*a.begin()).i]=cnt;a.erase(a.begin());     //已经将数纪录下来防止重复使用所以删掉；for(int i=2;i<=n;i++){set<wazxy>::iterator it;x.num=xx+k+1;it=a.lower_bound(x);    //若搜不到则返回.end；if(it!=a.end()){         //如果搜到了；position[(*it).i]=cnt;   //记录当前操作次数xx=(*it).num;      a.erase(it); continue;  }cnt++;        //如果搜不到操作次数+1，进入下一个操作的开始it=a.begin();   position[(*it).i]=cnt;xx=(*it).num;a.erase(it);}printf("%d\n",cnt);   for(int i=1;i<=n;i++)  printf("%d ",position[i]);return 0;
}