描述
传送门：我是传送门
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 n,m,dn,m,d (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,…,an(1≤ai≤m)a1,a2,…,an(1≤ai≤m), where aiai is some minute when Monocarp wants to have a coffee break.
输出
In the first line, write the minimum number of days required to make a coffee break in each of the nn given minutes.
In the second line, print nn space separated integers. The ii-th of integers should be the index of the day during which Monocarp should have a coffee break at minute aiai. Days are numbered from 11. If there are multiple optimal solutions, you may print any of them.
样例
输入
4 5 3
3 5 1 2
输出
3
3 1 1 2
输入
10 10 1
10 5 7 4 6 3 2 1 9 8
输出
2
2 1 1 2 2 1 2 1 1 2
Note
In the first example, Monocarp can take two coffee breaks during the first day (during minutes 11 and 55, 33 minutes will pass between these breaks). One break during the second day (at minute 22), and one break during the third day (at minute 33).
In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.
思路
每天有m分钟，A先生喜欢喝咖啡，但是两次喝咖啡的时间至少要间隔d分钟，每次喝咖啡需要1分钟，共有n种喝咖啡的时间可供选择
输出至少需要几天，以及第i杯咖啡是在第几天喝的
又是一次有了大致想法但是由于不太了解STL的用法而没办法A掉的题······
不知道set.lower_bound()这种用法
set+lower_bound 就可以解决了
代码
1 /* 2 *========================================================== 3 * 4 * Filename: C.cpp 5 * 6 * Link: http://codeforces.com/contest/1041/problem/C 7 * 8 * Version: 1.0 9 * Created: 2018/09/16 18时50分11秒 10 * Revision: none 11 * Compiler: g++ 12 * 13 * Author: 杜宁元 (https://duny31030.top/), duny31030@126.com 14 * Organization: QLU_浪在ACM 15 * 16 *========================================================== 17 */ 18 #include <bits/stdc++.h> 19 using namespace std; 20 #define clr(a, x) memset(a, x, sizeof(a)) 21 #define rep(i,a,n) for(int i=a;i<=n;i++) 22 #define pre(i,a,n) for(int i=n;i>=a;i--) 23 #define ll long long 24 #define max3(a,b,c) fmax(a,fmax(b,c)) 25 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 26 const double eps = 1e-6; 27 const int INF = 0x3f3f3f3f; 28 const int mod = 1e9 + 7; 29 const int N = 200100; 30 int n,m,d; 31 int ans[N],a[N]; 32 set<pair<int,int> > q; 33 pair<int,int> p; 34 int main() 35 { 36 ios 37 #ifdef ONLINE_JUDGE 38 #else 39 freopen("in.txt","r",stdin); 40 // freopen("out.txt","w",stdout); 41 #endif 42 scanf("%d %d %d",&n,&m,&d); 43 rep(i,1,n) 44 { 45 scanf("%d",&a[i]); 46 p = make_pair(a[i],i); 47 q.insert(p); 48 } 49 int cnt = 0; 50 while(!q.empty()) 51 { 52 ++cnt; 53 int pos = q.begin()->second; 54 ans[pos] = cnt; 55 q.erase(q.begin()); 56 while(1) 57 { 58 p = make_pair(a[pos]+1+d,0); 59 set<pair<int,int> >::iterator it; 60 it = q.lower_bound(p); 61 if(it == q.end()) 62 break; 63 pos = it->second; 64 q.erase(it); 65 ans[pos] = cnt; 66 } 67 } 68 printf("%d ",cnt); 69 rep(i,1,n) 70 { 71 printf("%d ",ans[i]); 72 } 73 printf(" "); 74 fclose(stdin); 75 // fclose(stdout); 76 return 0; 77 }