【CF1041C】 Coffee Break
题目
题意翻译
题目大意：
给定nn个数和一个kk，这nn个数都不超过mm
每次从没被去掉的数里面选一个数aa，去掉aa，然后可以任意一个b(b>a+k)b(b>a+k)，然后去掉任意一个c(c>b+k)c(c>b+k)，以此类推
问最少能选多少个aa，然后输出每个数都是选第几个aa的时候被去掉的
输入格式：
一行三个整数n,m,kn,m,k
再一行nn个整数，表示给定的数
输出格式：
第一行一个整数，表示最少选aa的个数
第二行nn个整数，表示每个数都是选第几个aa时被去掉的
题目描述
Recently Monocarp got a job. His working day lasts exactly m m minutes. During work, Monocarp wants to drink coffee at certain moments: there are n n minutes a_1, a_2, \dots, a_n a
1
,a
2
,…,a
n
, 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 a_i a
i
, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least d d minutes pass between any two coffee breaks. Monocarp also wants to take these n n 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 d d minutes pass between the end of any working day and the start of the following working day.
For each of the n n 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 n , m m , d d (1 \le n \le 2\cdot10^{5}, n \le m \le 10^{9}, 1 \le d \le m) (1≤n≤2⋅10
5
,n≤m≤10
9
,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 n n distinct integers a_1, a_2, \dots, a_n a
1
,a
2
,…,a
n
(1 \le a_i \le m) (1≤a
i
≤m) , where a_i a
i
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 n n given minutes.
In the second line, print n n space separated integers. The i i -th of integers should be the index of the day during which Monocarp should have a coffee break at minute a_i a
i
. Days are numbered from 1 1 . If there are multiple optimal solutions, you may print any of them.
输入输出样例
输入样例#1： 复制
4 5 3
3 5 1 2
输出样例#1： 复制
3
3 1 1 2
输入样例#2： 复制
10 10 1
10 5 7 4 6 3 2 1 9 8
输出样例#2： 复制
2
2 1 1 2 2 1 2 1 1 2
说明
In the first example, Monocarp can take two coffee breaks during the first day (during minutes 1 1 and 5 5 , 3 3 minutes will pass between these breaks). One break during the second day (at minute 2 2 ), and one break during the third day (at minute 3 3 ).
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.
思路
这道题乍一看是要用贪心的，因为对于每一天的每一个时间点，如果这一天能塞下这个时间点，那么对于下一天如果塞这个时间点必定更优。所以只要在每一天塞下最多的就行了。即先排一遍序，从第一个开始塞入每一天中，直到所有元素都被选中。
但是！！！
由于数据非常恶心，所以普通的从 1 开始搜索的策略是不可行的，肯定超时。那么就要考虑二分查找，用二分找到第一个满足条件的元素，再向后一个个寻找第一个未使用的元素，直到这一天塞不下停止。
但是！！！
程序依然在这里跑超时了…然后只能再进行优化，将每一天的最初元素从上一天得最初元素得后一个开始找，这样就可以跑过了。
代码
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200010
struct data
{
int val,id;
bool operator<(const data d)const
{
return val<d.val;
}
}x;
int n,m,d,pos[MAXN];
set<data> a;
int main()
{
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n;++i)
{
scanf("%d",&x.val);x.id=i;
a.insert(x);
}
int now=(*a.begin()).val,cnt=1;
pos[(*a.begin()).id]=1;
a.erase(a.begin());
for(int i=2;i<=n;++i)
{
data x;x.val=now+d+1;
auto p=a.lower_bound(x);
if(p!=a.end())
{
pos[(*p).id]=cnt;
now=(*p).val;
a.erase(p);
continue;
}
++cnt;
p=a.begin();
pos[(*p).id]=cnt;
now=(*p).val;
a.erase(p);
}
printf("%d\n",cnt);
for(int i=1;i<=n;++i)printf("%d ",pos[i]);
}