[POJ3197]Stall Reservations (贪心)
2024-08-28 12:06:29
题意
(来自洛谷)
约翰的N(l<N< 50000)头奶牛实在是太难伺候了,她们甚至有自己独特的产奶时段.当 然对于某一头奶牛,她每天的产奶时段是固定的,为时间段A到B包括时间段A和时间段B.显然,约翰必须开发一个调控系统来决定每头奶牛应该被安排到哪个牛棚去挤 奶,因为奶牛们显然不希望在挤奶时被其它奶牛看见.
约翰希望你帮他计算一下:如果要满足奶牛们的要求,并且每天每头奶牛都要被挤过奶,至少需要多少牛棚 •每头牛应该在哪个牛棚被挤奶。如果有多种答案,你只需任意一种即可。
分析
一道比较经典的贪心题,整体还是很简单的,只是我太菜。
个人感觉这道题是区间覆盖的升级版?
就是要满足所有的区间都被覆盖,求开区间线(就是这题牛棚)的个数
我一开始是N2做的,但是50000的数据过不了
后面借鉴了一下李煜东的std
用小根堆做掉了
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
#define N 50005
using namespace std; int n,num;
struct COW {
int l, r, id,ans;
bool operator <(const COW x)
const {
return l < x.l;
}
}cow[N];
int ans[N];
priority_queue<pair<int, int> > s; int main()
{
//freopen("testdata.in", "r", stdin);
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
cow[i].id = i;
scanf("%d%d", &cow[i].l, &cow[i].r);
}
sort(cow + , cow + + n);
for (int i = ; i <= n; i++)
{
int total = s.size();
if (total && -s.top().first < cow[i].l)
{
cow[i].ans = s.top().second;
s.pop();
s.push(make_pair(-cow[i].r, cow[i].ans));
continue;
}
cow[i].ans = ++num;
s.push(make_pair(-cow[i].r, num));
}
printf("%d\n",s.size());
for (int i = ; i <= n; i++) ans[cow[i].id] = cow[i].ans;
for (int i = ; i <= n; i++) printf("%d\n", ans[i]);
return ;
}
PS:POJ炸了
最新文章
- Sample a balance dataset from imbalance dataset and save it(从不平衡数据中抽取平衡数据,并保存)
- canvas drag 实现拖拽拼图小游戏
- ruby迭代器枚举器
- (转载)php获取form表单中name相同的表单项
- POJ-2386(深广搜基础)
- image.xx.com 通过haproxy 跳转到内部图片服务器
- shell脚本之不同系统上ftp交互使用
- zabbix邮箱报警设置&;问题汇总
- openstack--1--基础环境搭建
- Android app widget中实现跑马灯效果(非widget部件也实用)
- linux命令中which、whereis、locate有什么区别?
- DOS中符号的英文对照
- centos(7) 使用yum进行安装lamp环境
- NHibernate初学四之关联一对一关系
- gevent协程、select IO多路复用、socketserver模块 改造多用户FTP程序例子
- POJ 1741 树分治
- Linux下mongodb
- [Luogu 3958] NOIP2017 D2T1 奶酪
- Python学习笔记 - day7 - 类
- 【POJ 2406 Power Strings】
热门文章
- Android 第二波
- base | AtomicIntegerT类
- java.lang.RuntimeException: Unable to instantiate org.apache.hadoop.hive.metastore.HiveMetaStoreClient
- zookeeper 学习 zookeeper下载部署
- 彻底明确怎样设置minSdkVersion和targetSdkVersion
- 5336: [TJOI2018]party
- node.js版本管理
- k8s 英文文档翻译
- BZOJ4456/UOJ#184[Zjoi2016]旅行者 分治 最短路
- img-html-2