畜栏预定【贪心+小根堆】

畜栏预定【贪心+小根堆】

毫无疑问这是一个贪心思想, 应该是活动安排那个题的拓展,

本题的做法是:

1.将所有牛按开始吃草的时间排序

2.用小根堆维护当前所有畜栏的最后一头牛吃草结束的时间

3.如果当前的牛可以安排在堆顶畜栏,则将其安排进去,否则创建以个新的畜栏

反证法,假设存在一种方案,使得需要的畜栏数量更少,记其需要的畜栏数量是 m。

考虑在上述做法中,第一次新建第 m+1 个畜栏的时刻,不妨设当前处理的是第 i头牛。

由于所有牛是按开始时间从小到大排好序的,所以现在前 m 个畜栏中最后一头牛的开始时间一定小于等于第 ii 头牛的开始时间。

而且前 m 个畜栏中最小的结束时间大于等于第 ii 头牛的开始时间,所以前 m 个畜栏里最后一头牛的吃草区间一定都包含第 i 头牛的开始时间,所以我们就找到了 m+1个区间存在交集,所以至少需要 m+1 个畜栏,矛盾。

所以上述做法可以得到最优解,证毕。

可以的到当最小的结束时间都不满足条件,那么只能添加新的畜栏。

贴上代码


  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 typedef pair<int, int> PII;
  7 const int N = 5e5 + 5;
  8 int n, id[N];
  9 
 10 pair<PII, int> cows[N];
 11 
 12 int main(){
 13     cin >> n;
 14     for(int i = 0; i < n; ++ i){
 15         cin >> cows[i].first.first >> cows[i].first.second;
 16         cows[i].second = i;
 17     }
 18 
 19     sort(cows, cows + n);//按开始时间排序,和活动按安排差不多
 20     priority_queue<PII, vector<PII>, greater<PII> >heap;//这是一个小根堆用来维护每个畜栏的最小结束时间
 21     for (int i = 0; i < n; ++ i){
 22         if (heap.empty() || heap.top().first >= cows[i].first.first){//根据贪心可以证明,当最小的结束时间都不满足条件那么必须添加新的
 23             PII stall = make_pair(cows[i].first.second, heap.size());
 24             id[cows[i].second] = stall.second + 1;
 25             heap.push(stall);
 26         }
 27         else {
 28             auto stall = heap.top();
 29             heap.pop();
 30             stall.first = cows[i].first.second;
 31             id[cows[i].second] = stall.second + 1;
 32             heap.push(stall);
 33         }
 34     }
 35     cout << heap.size() << endl;
 36     for(int i = 0; i < n; ++ i) cout << id[i] << endl;
 37     return 0;
 38 }
上一篇:k8s命令脚本1-快捷查看所有pod、services、deployment、pv、pvc、ep


下一篇:蜗牛慢慢爬 LeetCode 36.Valid Sudoku [Difficulty: Medium]