http://poj.org/problem?id=1083
题意:搬桌子,给出a,b,表示从a搬到b,至少需要多少时间才能完成所有搬运任务
注意:搬出来走廊时,从开始到结束这段时间,所影响到的房间不可以同时作为搬运任务的区间点
贪心代码:
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
struct Room{
int x, y;
}room[405];
bool hash[405];
bool cmp (Room a, Room b) //按区间开端x排序,求区间最多覆盖次数
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
int n, i, t, temp, j, res;
cin >> t;
while (t--)
{
cin >> n;
for (i = 0; i < n; i++)
{
cin >> room[i].x >> room[i].y;
if (room[i].x > room[i].y) //每个区间开端为x,末端为y,y必须大于等于x
{
int t = room[i].x;
room[i].x = room[i].y;
room[i].y = t;
}
if (room[i].x % 2 == 0)//观察图可知,开端x是偶数时,会使得x-1的位置不可用
room[i].x--;
if (room[i].y % 2 == 1)//观察图可知,末端y是奇数时,会使得y+1的位置不可用
room[i].y++;
}
/*for (i = 0; i < n; i++)
cout << room[i].x << ' ' << room[i].y << "-----\n";*/
sort (room, room+n, cmp);
res = 0;
memset (hash, true, sizeof(hash));
for (i = 0; i < n; i++)
{
if (hash[i]) //往下寻找没有被覆盖其他区间
{
res++; //记录被覆盖的区间数
temp = room[i].y; //记录临时区间尾
for (j = i + 1; j < n; j++)
if (hash[j])
if (room[j].x > temp) //该区间没有发生交叉则标记为false
hash[j] = false, temp = room[j].y; //区间尾发生变化
}
}
cout << res*10 << endl;
}
return 0;
}
计数统计代码:【适合用于编号只有整数的题目,如The Skyline Problem 那题,http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1505】
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
int main()
{
int room[405];
int t, i, n, a, b, temp, maxs;
cin >> t;
while (t--)
{
memset (room, 0, sizeof(room));
maxs = 0;
cin >> n;
for (i = 0; i < n; i++)
{
cin >> a >> b;
if (a > b) //对于下面的for循环,必须要b大于等于a
temp = a, a = b, b = temp;
if (!(a&1)) //同理,a是偶数的时候也会影响a-1的位置
a--;
if (b&1) //同理,b是奇数的时候也会影响b+1的位置
b++;
if (b > maxs)
maxs = b;
//cout << a << ' ' << b << endl;
for (int x = a; x <= b; x++)
room[x]++;
}
cout << (*max_element (room, room+maxs+1))*10 << endl; //返回至少区间覆盖数
}
return 0;
}
分享到:
相关推荐
【标题】"POJ1083-Moving Tables"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目主要考察的是算法设计和问题解决能力,通常在ACM/ICPC(国际大学生程序设计竞赛...
**POJ1083 Moving Tables** 在这个问题中,我们需要在一个由400个房间组成的环境中移动桌子,房间布局如下:奇数编号的房间位于北侧,偶数编号的房间位于南侧,两者之间由一条走廊分隔。移动桌子时,为了避免两张...
晋城市-晋城市-街道行政区划_140500_Shp数据-wgs84坐标系.rar
内容概要:本文档汇总了46个经典的Linux面试题及其答案,涵盖了Linux系统操作的基本命令和概念。内容涉及路径表示与目录切换、进程管理、文件和目录操作、权限设置、文件内容查看等多个方面。每个问题都给出了明确的答案,旨在帮助面试者全面掌握Linux命令行操作技能,同时加深对Linux系统原理的理解。 适合人群:准备Linux相关职位面试的求职者,尤其是有一定Linux基础但缺乏实战经验的技术人员。 使用场景及目标:①用于个人自学或面试前复习,巩固Linux基础知识;②作为企业内部培训资料,帮助员工提升Linux操作水平;③为初学者提供系统化的学习指南,快速入门Linux命令行操作。 其他说明:文档内容侧重于实际操作命令的讲解,对于每个命令不仅提供了基本语法,还解释了具体应用场景,有助于读者更好地理解和记忆。建议读者在学习过程中多加练习,将理论知识转化为实际操作能力。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
内容概要:本文提供了10道华中杯C++竞赛真题的详细解析,涵盖多种基础编程技能与高级特性。每道题目不仅包含详细的解题思路和代码实现,还附带了完整的运行结果。具体包括:函数参数传递(指针实现)、宏定义比较、数组元素打印、几何图形面积计算、字符串拼接、素数判断、多态的实现、文件操作、简单计算器和学生信息管理。这些题目帮助读者深入理解C++语言的核心概念和技术应用。 适合人群:对C++有一定了解的编程初学者和中级开发者,尤其是准备参加编程竞赛的学生或程序员。 使用场景及目标:①作为编程练习和竞赛备考资料,帮助读者掌握C++的基本语法和常用算法;②通过实际代码示例加深对C++特性的理解,如指针、宏定义、面向对象编程等;③提供完整的源码供读者参考和调试,增强动手能力和问题解决能力。 阅读建议:建议读者按照题目难度逐步学习,先理解题目背景和解题思路,再仔细研读代码实现,并尝试独立编写和调试代码。同时,鼓励读者扩展思考,探索更多可能的解决方案,以提高编程水平。
街道级行政区划shp数据,wgs84坐标系,直接使用。
街道级行政区划shp数据,wgs84坐标系,直接使用。
通用计算器的设计FPGA.doc
晋城市-沁水县-街道行政区划_140521_Shp数据-wgs84坐标系.rar
赤峰市-松山区-街道行政区划_150404_Shp数据-wgs84坐标系.rar
JAVA中Stream编程常见的方法分类
街道级行政区划shp数据,wgs84坐标系,直接使用。
大同市-浑源县-街道行政区划_140225_Shp数据-wgs84坐标系.rar
包头市-昆都仑区-街道行政区划_150203_Shp数据-wgs84坐标系.rar
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
内容概要:本文详细介绍了车载电子电器架构中的网络拓扑开发,涵盖开发概述、车载网络总线、网络设计原则、开发流程及小结。网络拓扑开发是汽车电气架构中的重要环节,旨在设计合理的网络结构以确保各电子控制单元(ECU)之间的高效通信。文中阐述了通信协议选择、网络节点布局、通信介质选择、拓扑结构设计及安全性考虑等关键要素,并强调了仿真与验证的重要性。此外,还讨论了网络设计的原则,如前瞻性、兼容性、拓展性、实时性、可靠性和安全性,以及网络负载的优化措施。最后,总结了网络拓扑开发的流程,包括需求分析、设计、仿真验证、优化迭代及文档记录。 适合人群:汽车电子工程师、各域功能工程师、子系统及零部件开发者、测试工程师等从事汽车电气架构开发的相关人员。 使用场景及目标:①帮助工程师理解汽车网络拓扑开发的关键步骤和技术要点;②指导工程师在设计过程中遵循科学合理的设计原则,确保网络拓扑的高性能和可靠性;③提供网络负载优化的措施,确保数据传输的实时性和效率。 其他说明:网络拓扑开发不仅需要考虑技术层面的因素,还需兼顾成本效益,以适应不断变化的市场需求和技术趋势。本文建议读者在实践中不断积累经验,关注新技术的应用和发展,以应对未来的挑战和机遇。
内容概要:本文探讨了智能分析AI Agent在金融行业的先进实践与展望,指出金融行业在经营分析领域面临的现状和痛点,包括管理团队无法快速获得深度结论,业务团队面对BI产品学习门槛高、依赖人工等问题。文中介绍了智能分析AI Agent相较于传统解决方案的技术创新,如数据建模右移、基于虚拟层的数据编织、指标平台与大模型组合方案等,强调其在降低使用门槛、提高效率和增强交互性方面的优势。同时,文章展示了智能分析AI Agent在交互式指标问询、自动分析报告生成等应用场景中的价值,并对未来的发展进行了展望。 适合人群:金融行业的管理层、业务分析师、数据科学家以及对金融科技感兴趣的从业者。 使用场景及目标:①帮助管理层快速获取数据背后的深层次原因和结论;②降低业务团队使用数据分析工具的门槛,提高工作效率;③实现数据的自动化处理和分析,减少人工干预;④推动企业内部的数据民主化,使更多员工能够参与数据分析和决策。 阅读建议:本文不仅提供了智能分析AI Agent的技术细节,还结合实际案例展示了其应用效果,因此在阅读过程中应重点关注技术创新点及其对企业管理和业务流程的具体影响。