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 + ;

struct node

{

    int id, num, day;

    node(int id=,int num=,int day=):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=;i<=n;i++)

    {

        int x;

        scanf("%d", &x);

        ex[i] = node(i, x, );

    }

    sort(ex + , ex +  + n, cmp);

    priority_queue<node>que;

    int cnt = ;

    ex[].day = ;

    que.push(ex[]);

    for(int i=;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 + , ex +  + n, cmp1);

    printf("%d\n", cnt);

    for (int i = ; i <= n; i++) printf("%d ", ex[i].day);

    printf("\n");

    return ;

}