acwing111-畜栏预定

news/2024/10/30 11:22:07/

算法分类:

区间分组的应用 贪心


问题描述

有 N 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。

给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B,每头牛在 [A,B]这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第 1 行:输入一个整数 N。

第 2..N+1 行:第i+1 行输入第 i头牛的开始吃草时间 A 以及结束吃草时间 B,数之间用空格隔开。

输出格式

第 1 行:输出一个整数,代表所需最小畜栏数。

第 2..N+1 行:第 i+1 行输出第 i头牛被安排到的畜栏编号,编号是从 1 开始的 连续 整数,只要方案合法即可。

数据范围

1≤N≤50000,
1≤A,B≤1000000

输入样例:

5
1 10
2 4
3 6
5 8
4 7

输出样例:

4
1
2
3
2
4

实现步骤:

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

经典的区间分组问题。


实现代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
//cows.x.x为当前牛的吃草开始时间 cows.x.y为当前牛的吃草结束时间 cows.y为牛的编号
pair<PII,int> cows[N];
int n;
int id[N];
int main(){cin >> n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;cows[i].x.x = l;cows[i].x.y = r;cows[i].y = 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().x>=cows[i].x.x){id[cows[i].y] = heap.size();heap.push({cows[i].x.y,heap.size()});}else{auto stall = heap.top();heap.pop();stall.x = cows[i].x.y;heap.push(stall);id[cows[i].y] = stall.y;}}cout<<heap.size()<<endl;for(int i=0;i<n;i++) cout<<id[i]+1<<endl;return 0;
}


http://www.ppmy.cn/news/9810.html

相关文章

【java篇】反射机制简单理解

学到JDBC后&#xff0c;使用到反射机制&#xff0c;所以回顾反射机制相关知识点&#xff1b; 文章目录 文章目录 什么是反射机制&#xff1f; 如何理解反射呢&#xff1f; 总结 一、Java反射机制是什么&#xff1f; 二、Java反射机制中获取Class的三种方式及区别&#xff1f; 三…

Acwing---795.前缀和

前缀和1.题目2.基本思想3.代码实现4.总结1.题目 输入一个长度为n的整数序列。 接下来再输入m个询问&#xff0c;每个询问输入一对l&#xff0c;r。 对于每个询问&#xff0c;输出原序列中从第l个数到第 r 个数的和。 输入格式 第一行包含两个整数n和m。 第二行包含n个整数&am…

python简单介绍及基础知识(二)

♥️作者&#xff1a;小刘在这里 ♥️每天分享云计算网络运维课堂笔记&#xff0c;疫情之下&#xff0c;你我素未谋面&#xff0c;但你一定要平平安安&#xff0c;一 起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽放&#xff0c;…

Linux学习笔记——Nginx安装部署

5.3、Nginx安装部署 5.3.1、简介 Nginx&#xff08;engine x&#xff09;是一个高性能的HTTP和反向代理Web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。 同Tomcat一样&#xff0c;Nginx可以托管用户编写的WEB应用程序成为可访问的网页服务&#xff0c;同时也可以作为…

两数之和【每日一题】

⭐前言⭐ ※※※大家好&#xff01;我是同学〖森〗&#xff0c;一名计算机爱好者&#xff0c;今天让我们进入刷题模式。若有错误&#xff0c;请多多指教。更多有趣的代码请移步Gitee &#x1f44d; 点赞 ⭐ 收藏 &#x1f4dd;留言 都是我创作的最大的动力&#xff01; 合抱之木…

ThinkPHP使用小技巧之Request封装快捷方法总结

think\Request为一些常用的操作方法封装了函数&#xff0c;便于使用。 可使用request()全局助手函数来获取。TP版本^6.1。 目录 包含如下&#xff1a; 1.获取请求参数 2.获取客户端IP地址 3.当前请求中的port参数 4.获取当前的请求类型&#xff0c;返回大写字符 5.判断请…

使用Sivarc使PLC程序标准化

前言 由于公司最近做的项目都是同样的&#xff0c;并且都采用S7-1500/S7-1200 与G120 系列做为主控系统&#xff0c;所以我一直在思考一个问题&#xff1a;如何标准化并且快速的编程调试。这样可以极大的缩短项目的调试周期&#xff0c;减少公司工程成本&#xff0c;同时也免去…

ATJ2158 LRADC的使用

LRADCLRADC对应引脚LRADC采样电压范围及位数使用LRADC涉及到的驱动文件如何使用不同的LRADC通道LRADC对应引脚 LRADC对应引脚备注LRACDC1WIO0/WIO1LRACDC2GPIO8/GPIO20LRACDC3GPIO9/GPIO21LRACDC4GPIO35LRACDC5GPIO5LRACDC6无没有找到相应的引脚LRACDC7GPIO63 LRADC采样电压范…