C. Coffee Break 贪心 思维 有点难 有意思

C. Coffee Break

这个贪心之前好像写过，还是感觉挺难的，有点不会写。

这个题目大意是：给你一个数列n个元素，然后给你一天的时间，给你一个间隔时间d，

问你最少要用多少天可以把这个数列的所有元素放进去，注意元素之间必须相隔大于等于d，还有就是假设每一天之间的间隔大于d

解法：

借助队列来解题，

首先给这个元素按照元素大小来拍个序，贪心优先考虑小的，优先把小的放进去，

然后第一天肯定是要开一天的，如何后面的比这个大那就新开一天，否则就可以直接继承这一天。

这个就是解题思路，我觉得我应该要会这个思维题，但是并没有写出来，反而想的特别乱，这样不太对啊。

再仔细想想这个题目其实遇到很多很类似的，就是用优先队列来维护这个num最小值，能放进放，不能放进新开一天

和网络流的魔术球问题的建图条件很像。

#include <cstring>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <string>
#include <bitset>
#include <algorithm>
#include <map>
#include <vector>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct node
{
    int id, num, day;
    node(int id=0,int num=0,int day=0):id(id),num(num),day(day){}
    bool operator<(const node &a)const
    {
        return a.num < num;
    }
}ex[maxn];
bool cmp(node a,node b)
{
    return a.num < b.num;
}
bool cmp1(node a,node b)
{
    return a.id < b.id;
}
int main()
{
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d", &x);
        ex[i] = node(i, x, 0);
    }
    sort(ex + 1, ex + 1 + n, cmp);
    priority_queue<node>que;
    int cnt = 1;
    ex[1].day = 1;
    que.push(ex[1]);
    for(int i=2;i<=n;i++)
    {
        node now = que.top(); que.pop();
        int x = now.num;
        if (x + d < ex[i].num) {
            ex[i].day = now.day;
            que.push(ex[i]);
        }
        else {
            cnt++;
            ex[i].day = cnt;
            que.push(ex[i]);
            que.push(now);
        }
    }
    sort(ex + 1, ex + 1 + n, cmp1);
    printf("%d
", cnt);
    for (int i = 1; i <= n; i++) printf("%d ", ex[i].day);
    printf("
");
    return 0;
}