Coffee Break(Set,贪心）

Coffee Break

题意

给你个数分组，分组的数量尽可能的少，且每组中的两个数最少相差;

思路：

从小到大排序，从个开始，找比第1个大的第一个数，在x等于这个刚找到的数，在找比它大的第一个数。一天能经可能的多放。第二天从新开始，但是在第一天的就不能在第二天了。。。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=2*1e5+10;
int a[M];
map<int,int>mp;
int n,m,d;
int main( )
{
    while(~scanf("%d%d%d",&n,&m,&d))
    {
        set<int> s;//set默认从小到大排序
        set<int>::iterator it;//指针
        mp.clear( );
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            s.insert(a[i]);
            mp[a[i]]=i;
        }
        int ans=1;
        int cnt=0;
        while(s.size( ))
        {
            it=s.lower_bound(cnt);//找出比cnt大或等于的第一个数
            if(it==s.end( ))//重新开一天
            {
                ans++;
                cnt=0;
            }
            else
            {
                mp[*it]=ans;
                s.erase(*it);//删除这个数,不删除的话，一个数可能会出现在不同的天数
                cnt=*it+d+1;//这个数加上d+1
            }
        }
        printf("%d\n",ans);
        for(int i=0;i<n;i++)
        {
            printf("%d%c",mp[a[i]],i==n-1?'\n':' ');
        }
    }
    return 0;
}