AcWing 111. 畜栏预定

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 111. 畜栏预定原题链接简单

作者：

yxc , 2019-02-26 01:13:37 , 所有人可见 , 阅读 7767

79

22

算法

(贪心) $O(nlogn)$

我们先介绍做法，再证明其正确性。

算法步骤：

将所有牛按开始吃草的时间排序；
用小根堆维护当前所有畜栏的最后一头牛的吃草结束时间；
如果当前的牛可以安排在堆顶的畜栏中，则将其安排进去，否则就新建一个畜栏；

证明：

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

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

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

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

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

时间复杂度

排序的时间复杂度是 $O(nlogn)$ 。
依次枚举每头牛的过程中，只涉及到常数次堆的操作，时间复杂度至多是 $O(logn)$ 。

所以总时间复杂度是 $O(nlogn)$ 。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int,int> PII;
const int N = 50010;

int n;
int id[N];
pair<PII, int> cows[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> cows[i].first.first >> cows[i].first.second;
        cows[i].second = i;
    }

    sort(cows, cows + n);

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (int i = 0; i < n; i ++ )
    {
        if (heap.empty() || heap.top().first >= cows[i].first.first)
        {
            PII stall = {cows[i].first.second, heap.size()};
            id[cows[i].second] = stall.second;
            heap.push(stall);
        }
        else
        {
            auto stall = heap.top();
            heap.pop();
            stall.first = cows[i].first.second;
            id[cows[i].second] = stall.second;
            heap.push(stall);
        }
    }

    cout << heap.size() << endl;
    for (int i = 0; i < n; i ++ ) cout << id[i] + 1 << endl;
    return 0;
}

35 评论

上下求索 2022-04-20 17:29

注解版，供家人们参考

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
const int N = 5e5+10;
using PII = pair<int,int>;
// 存储<区间，奶牛编号>
pair<PII,int> cows[N];
int id[N];

int main()
{
    int n;cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>cows[i].x.x>>cows[i].x.y;
        cows[i].y=i;
    }

    // 按左端点由小到大进行排序
    sort(cows,cows+n,[](const auto& a,const auto& b){
        return a.x.x<b.x.x;
    });

    // 堆中存放的元素为<当前分组内区间右端点的最小值，分组编号>
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    // 按左端点从小到大枚举即可
    for(int i=0;i<n;++i)
    {
        // 堆为空或者堆中右端点的最小值大于等于当前区间的左端点，表示区间相交，需要新开一个分组，再把当前区间放进去
        if(heap.empty()||heap.top().x>=cows[i].x.x)
        {
            // 新区间的右端点，分组编号
            PII stall={cows[i].x.y,heap.size()};
            // 奶牛i被存放到分组stall.y中
            id[cows[i].y]=stall.y;
            // 添加新的分组
            heap.push(stall);
        }
        //  否则表示当前区间可以添加到右端点最小值的分组中，则将右端点最小值进行更新为当前区间的右端点
        else
        {
            auto stall=heap.top();heap.pop();
            // 更新合并区间后新的右端点
            stall.x=cows[i].x.y;
            // 奶牛i被存放在分组stall.y中
            id[cows[i].y]=stall.y;
            // 将更新右端点之后的分组，重新添加到堆中
            heap.push(stall);
        }
    }

    cout<<heap.size()<<endl;
    for(int i=0;i<n;++i)cout<<id[i]+1<<endl;
    return 0;
}

Turing_Sheep 2023-11-07 08:31

multiset+二分

#include<bits/stdc++.h>
using namespace std;
typedef pair<pair<int,int>,int> piii;
const int N = 1e5 + 10;
multiset<piii>t;
int st[N];
int n;
void solve()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        t.insert({{a, b},i});
    }
    int cnt = 0;
    while(t.size())
    {
        cnt ++;
        auto cur = t.begin();
        while(cur != t.end())
        {
            st[cur->second] = cnt;
            auto tmp = t.lower_bound({{cur->first.second + 1,-1}, -1});
            t.erase(*cur);
            cur = tmp;
        }
    }
    cout << cnt << endl;
    for(int i = 0; i < n; i ++)
        cout << st[i] << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while(t--)
    solve();
}

蒻犇_ZYK 2023-09-08 22:22

哦，小根堆真的是太妙了

Pinguier 2023-01-06 16:08

为什么这里一定要先读入编号的畜栏号输出的时候是id+1啊友友们

Susanna 2023-01-19 21:05

因为题目的组的编号是从1开始的，数组是从0开始的

月下飞天镜 2021-03-08 14:02

畜栏预定这道题为什么不用重载运算符呢，小根堆排序的数据类型是自定义的呀

Dream_56 2022-02-06 21:21

因为pair可以直接用比较运算符进行运算

月下飞天镜 2022-02-11 13:49 回复了 Dream_56 的评论

感谢

一只小蜜蜂呀. 5天前 ·江苏

请问为什么一定要按照开始时间排序？用结尾时间排序为什么就错误了？

Flamze 5个月前

有没有大佬帮看一下，思路是不用堆，就每次安排的时候只要找到了当前牛栏的最后结束时间小于当前牛的开始吃草时间就放进去（不用堆优化版本），但是答案不对，找了半天没找到代码的问题，求帮忙看一下，代码哪里不对。

#include <iostream>
#include <algorithm>
using namespace std;

int N;
const int maxn = 5e5 + 10;
struct Node {
    int l, r;
    int id;
}nodes[maxn];

int tt[maxn], cnt = 0;
int ans[maxn];

bool cmp(Node node1, Node node2) {
    if (node1.l != node2.l)return node1.l < node2.l;
    return node1.r < node2.r;
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &nodes[i].l, &nodes[i].r);
        nodes[i].id = i;
    }
    sort(nodes + 1, nodes + 1 + N, cmp);

    for (int i = 1; i <= N; i++) {
        int j = 0;
        while (j < cnt) {//遍历牛栏已经存在的牛栏
            if (nodes[i].l >= tt[j+1]) {//如果能找到当前合适的牛栏
                ans[nodes[i].id] = j + 1;//把当前奶牛放进牛栏中
                tt[j + 1] = nodes[i].r;//更新当前牛栏的结束时间
                break;
            }
            j++;
        }
        if (j == cnt) {//代表没找到
            cnt++;//新增一个栏位
            ans[nodes[i].id] = cnt;
            tt[cnt] = nodes[i].r;
        }
    }

    printf("%d\n", cnt);
    for (int i = 1; i <= N; i++)printf("%d\n", ans[i]);

    return 0;
}

穩 8个月前

heap.top().first表示右端点？？？

rongyi 10个月前

#include <algorithm>
#include <array>
#include <functional>
#include <ios>
#include <iostream>
#include <queue>
#include <strings.h>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  int n = 0;
  cin >> n;
  // start, end, index
  vector<array<int, 3>> cows(n);
  for (int i = 0; i < n; i++) {
    cin >> cows[i][0] >> cows[i][1];
    cows[i][2] = i;
  }
  sort(cows.begin(), cows.end());

  int total = 0;
  vector<int> taken(n, 0);
  using i2 = array<int, 2>;
  // end time and index
  priority_queue<i2, vector<i2>, greater<i2>> pq;

  for (int i = 0; i < n; i++) {
    auto start = cows[i][0];
    auto end = cows[i][1];
    auto idx = cows[i][2];
    // 每次都去找之前最早结束的那个牛栏，找到就复用，找不到就
    // 新开一个牛栏，编号顺延
    // 什么情况下能用？这个牛栏里的牛结束吃草时间早于下一个牛开始的
    if (pq.empty() || pq.top()[0] >= start) {
      int next_idx = pq.size();
      pq.push({end, next_idx});
      taken[idx] = next_idx;
      total += 1;
    } else {
      // latest finished room, we can take
      // {endtime, root index}
      auto cur = pq.top();
      pq.pop();
      cur[0] = end;
      taken[idx] = cur[1];

      pq.push(cur);
    }
  }

  cout << total << endl;
  for (auto &val : taken) {
    cout << val + 1 << endl;
  }
  return 0;
}

Pinguier 2023-01-06 15:58

想问问这样写为什么不对呀有没有大佬帮忙看一下
for(int i=0;i[HTML_REMOVED]=cows[i].x.x){
heap.push({cows[i].x.y,heap.size()});
id[cows[i].y] = heap.size();
}
else{
heap.pop();
heap.push({cows[i].x.y,heap.size()+1});
id[cows[i].y] = heap.size();
}
}