ACM学习历程—HihoCoder1309任务分配(排序 && 贪心)

http://hihocoder.com/problemset/problem/1309

题目大意是给定n个任务的起始时间，求问最少需要多少台机器。

有一个贪心的策略就是，如果说对于一个任务结束，必然接一个开始时间最接近这个的比较合算。我们假想一个任务池，那么任务池中最早结束的那个，必然接剩余任务中最早开始的比赛合算（相同开始时间最早结束），而且假设这个任务是P，那么对于一个结束时间晚于P的任务，显然后面的一段时间是浪费的，同样对于一个开始时间晚于P的任务，前面一段是浪费的；

关键在于某个开始时间晚于P，但是结束时间早于P的任务Q，假设接上Q后，还能接一个X，但是接上P后，无法接上X。

首先，对于接P的情况，会导致Q和X，无法接上，或许需要重开一个机器，或者是任务池中存在另一个任务可以接上。对于接Q的情况，会导致P，无法接上，或许需要重开一个机器，或许任务池中存在一个任务可以接上。

对于需要重开一个机器的情况，两者的效果是等价的。那么假设，接Q的情况，任务池中存在另一个任务可以接P，必然，对于接P的情况，存在同样的任务可以接Q，因为P的开始时间早于Q，那么此情况下，两者亦是等价的。

所以，综上，剩余任务中最早开始的比赛合算（相同开始时间最早结束）。

于是只需要开始对所有任务按开始时间正序，次按结束时间正序排序。然后用一个优先队列（堆）维护任务池即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <vector>

#include <string>

#define LL long long

using namespace std;

const int maxN = ;

struct node

{

    int s, e;

}a[maxN];

bool cmp(node x, node y)

{

    if (x.s != y.s) return x.s < y.s;

    else return x.e < y.e;

}

int n;

void work()

{

    priority_queue<int, vector<int>, greater<int> > q;

    q.push();

    int k;

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

    {

        k = q.top();

        q.pop();

        if (k <= a[i].s) q.push(a[i].e);

        else q.push(a[i].e), q.push(k);

    }

    printf("%d\n", q.size());

}

int main()

{

    //freopen("test.in", "r", stdin);

    //freopen("test.out", "w", stdout);

    while (scanf("%d", &n) != EOF)

    {

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

            scanf("%d%d", &a[i].s, &a[i].e);

        sort(a, a+n, cmp);

        work();

    }

    return ;

}

巴特西

ACM学习历程—HihoCoder1309任务分配(排序 && 贪心)

最新文章

热门文章