描述
2010年上海世界博览会(Expo2010),是第41届世界博览会。于2010年5月1日至10月31日期间,在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市,让生活更美好”(Better City,Better Life)为主题,将充分探索21世纪城市生活。
这次世博会总投资达450亿人民币,创造了世界博览会史上的最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。
为了更好地接待在这期间来自世界各地的参观者,如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客户住宿定单,每张定单的内容包括要住宿的房间数,开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理,组委会希望对这些定单进行安排,目的是用尽可能少的房间来满足这些定单,以便空出更多的房间用于安排流动游客。
组委会请求DR.Kong来完成这个任务,对这些定单进行合理安排,使得满足这些定单要求的房间数最少。
假设:某个定单上的游客一旦被安排到某房间,在他预定住宿的期间内是不换房间的。为了简化描述,定单上的开始住宿时间为距离现在的第几天。例如,定单为(10,30,5)表示游客要求使用10个房间,第30天开始连住5天。
- 输入
- 第一行:T 表示有T组测试数据 每组测试数据第一行:N 表示定单数 每组测试数据接下来有N行,每行有三个整数 A B C 表示房间数,开始住宿时间和天数 1<=T<=100 1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10
- 输出
- 输出一个整数,为满足所有定单要求的最少房间数。
- 样例输入
-
1
3
3 10 4
4 9 3
3 12 6#include <stdio.h>
#include <string.h>
#define M 200
int day[M]; int main()
{
int t, n, r, s, span, i, max;
scanf("%d", &t);
while(t--){ max = ;
memset(day, , sizeof(day));
scanf("%d", &n);
while(n--){ scanf("%d %d %d", &r, &s, &span);
for(i = s; i < s+span; i++)
{
day[i] += r;
if(day[i] > max)
{
max = day[i];
} } }
printf("%d\n", max); }
return ;
}一开始用常规的方法:相交的区域相加,间隔的区域相减。但往深处考虑,其实就是找出这些区域的房间最大值
房间安排-nyoj168的更多相关文章
-
ACM 房间安排
房间安排 时间限制:3000 ms | 内存限制:65535 KB 难度:2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会.于2010年5月1日至10月31日期间, ...
-
nyoj 168 房间安排(区间覆盖)
房间安排 时间限制:3000 ms | 内存限制:65535 KB 难度:2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会.于2010年5月1日至10月31日期间, ...
-
ny168 房间安排
房间安排 时间限制:3000 ms | 内存限制:65535 KB 难度:2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会.于2010年5月1日至10月31日期间,在中 ...
-
[河南省ACM省赛-第三届] 房间安排 (nyoj 168)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=168 分析:找到一天中需要最多的房间即可 #include<iostream> ...
-
房间安排 (nyoj 168)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=168 分析:找到一天中需要最多的房间即可 #include<iostream> ...
-
NYOJ题目168房间安排
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAssAAAOTCAIAAADGwNmiAAAgAElEQVR4nOy9PY7cyLPufTchXwsZu9
-
The Accomodation of Students HDU - 2444 二分图判定 + 二分图最大匹配 即二分图-安排房间
/*655.二分图-安排房间 (10分)C时间限制:3000 毫秒 | C内存限制:3000 Kb题目内容: 有一群学生,他们之间有的认识有的不认识.现在要求把学生分成2组,其中同一个组的人相互不认 ...
-
[原]NYOJ-房间安排168
大学生程序代写 /*房间安排 时间限制:3000 ms | 内存限制:65535 KB 难度:2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会.于2010年5月1日至1 ...
-
Day 1 @ RSA Conference Asia Pacific &; Japan 2016
# 国内出发 早上8:45的航班,首次从深圳机场乘坐国际航班(先前去日本.欧洲都从香港走),就提前了3个小时出发. 乘taxi到机场30分钟不到,135元.到了T3 4号出发口,发现check-in的 ...
随机推荐
-
Java 集合框架
Java集合框架大致可以分为五个部分:List列表,Set集合.Map映射.迭代器.工具类 List 接口通常表示一个列表(数组.队列.链表 栈),其中的元素 可以重复 的是:ArrayList 和L ...
-
liMarquee演示12种不同的无缝滚动效果
很实用的一款liMarquee演示12种不同的无缝滚动效果 在线预览 下载地址 实例代码 <!DOCTYPE html> <html lang="zh-CN"&g ...
-
codeforces 86D : Powerful array
Description An array of positive integers a1, a2, ..., an is given. Let us consider its arbitrary su ...
-
dell ipmi sol
http://blog.arnoudvermeer.nl/post/52375062605/howto-setup-ipmi-sol-on-a-dell-r-series-server http:// ...
-
[CodeEdit--Sublime]一些好用的Plugins
Sublime Text 3 Plugins (**)packet control:plugin包管理器 (**)netuts-fetch: (**)markdown editing:Markdown ...
-
UIImagePickerController 如何显示中文界面
1: 添加中文的 Localizations Project --> Info --> Localizations 添加 "Chinese(Simplified)" ...
-
主席树套树状数组 动态区间第k小
先打上代码以后更新解释 #include <cstdio> #include <iostream> #include <algorithm> #include &l ...
-
正确地黑C
转载:http://tieba.baidu.com/p/3190068223?pn=1 本版暂时当作提纲,不做详细展开讨论,以后可能更新. 注意:本文主旨不是政治正确. 1.设计C的设计相对于同期来说 ...
-
【Unity技能】做一个简单的NPC
1. 写在前面 前几天我看到cgcookie一个教程.学习了下怎么依据已有人物模型制作一个仿版的NPC人物.感觉挺好玩的,整理一下放到博客里! 先看一下教程里面的终于效果. 是不是非常像个幽灵~ 以下 ...
-
session 与 cookie (一)
服务器信息临时存储 session篇 web.xml设置 <session-config> <session-timeout></session-timeout> ...