hdu 6180贪心

题意：有m个工程，一台机器在同一时间只能运行一个工程，告诉你每个工程的起始时间和结束时间，求出最少要多少个机器以及最小的机器总运行时间（机器开始了就不能停了，直到用完该台机器才停止）。

题解：由于这里可以使用多台机器，那么我们用起点排序也能够得到最小的k。（对比了下典型的区间调度问题，那个问题由于只有一台机器，所以必须用结束时间排序——尽早结束可以有更多的机会接触更多的时间区间）。然后题目要求最小的工作时间，这里我们只要保证一台机器运行的两个工程之间的时间间隔最小就可以了，也是一个贪心。一开始我用一个队列来维护机器的结束但是这是不行的，因为在判断是否需要新引入一台机器的时候，我们希望队列的首位为结束时间最早的机器；而当我们计算时间的时候，我们希望能有一个符合条件的结束时间最晚的机器来继续现在的工程。所以我们需要两个队列来维护，一个工作队列，一个空闲队列。

ac代码：

#include <iostream>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <functional>

#define N 100010

#define LL __int64

#define inf 0x3f3f3f3f

using namespace std;

const LL mod = 1e9 + ;

struct node {

    LL st, en;

}thing[N];

bool cmp1(node a, node b) {

    if (a.st == b.st) {

        return a.en < b.en;

    }

    return a.st < b.st;

}

int main() {

    cin.sync_with_stdio(false);

    int T;

    int n;

    cin >> T;

    while (T--) {

        cin >> n;

        priority_queue<LL>p;//空闲集合

        priority_queue<LL, vector<LL>, greater<LL> >q;//工作集合

        for (int i = ; i < n; i++) {

            cin >> thing[i].st >> thing[i].en;

        }

        LL ans = , sum = ;

        sort(thing, thing + n, cmp1);

        for (int i = ; i < n; i++) {

            node now = thing[i];

            while ((!q.empty()) && q.top() <= now.st) {

                p.push(q.top());

                q.pop();

            }

            if (!p.empty()) {

                int num = p.top();

                p.pop();

                sum += now.en - num;

                q.push(now.en);

            }

            else {

                ans++;

                sum += now.en - now.st;

                q.push(now.en);

            }

        }

        cout << ans << " " << sum << endl;

    }

    return ;

}

巴特西

hdu 6180贪心

最新文章

热门文章