[BZOJ1572][Usaco2009 Open]工作安排Job

首先，并不是同一个时刻保留获益最大的工作，因为可能闲着没事做，比方说： 
1 100
3 100
3 100

这样可以获利300。

接着，在当前时刻，我们肯定先挑利益最大的做。

但是有个截止时间很讨厌。我们不妨把问题转化一下：我们不着急着马上求出最优方案，我们把所有可能在最优工作安排集合当中的工作放在一起，然后逐步修改这个集合，到最后就是最优的安排集合了。

做法如下：

按照截止时间从小到大排序，用小根堆维护所有可能要做的工作。那么堆中的元素个数+1就是当前时间。遍历每一个工作。
  1. 如果当前工作的截止时间不超过当前时间的话，我们可以先去做这个工作，扔进堆里面。
  2. 如果当前工作的截止时间超过了当前时间的话，我们看看堆中获利最小的工作，如果比当前工作优，不做也罢；如果比当前工作劣，那么扔掉，把当前工作加进来。

最后的答案就是把堆中工作相加。

Hint:这题要用long long

P.S.:C++的priority_queue很好用！ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>

struct Job { int d, p; } a[100000];
inline bool operator<(const Job& lhs, const Job& rhs) { return lhs.d < rhs.d; }
int n;
std::priority_queue<int, std::vector<int>, std::greater<int> > heap;
int main()
{
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &a[i].d, &a[i].p);
  std::sort(a, a+n);

  for (int i = 0; i < n; ++i)
    if (a[i].d > static_cast<int>(heap.size()))
      heap.push(a[i].p);
    else if (a[i].p > heap.top())
    {
      heap.pop();
      heap.push(a[i].p);
    }
  long long ans = 0;
  while (!heap.empty())
  {
    ans += heap.top();
    heap.pop();
  }
  printf("%lld", ans);
}

Comments