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;
}
分享到:
相关推荐
【标题】"poj_1699.rar_1699_poj_poj1699" 提供的是一个关于POJ(编程在线判题系统)第1699题的解决方案,其中包含了该问题的代码实现和解题思路。POJ是一个流行的在线编程竞赛平台,它为参赛者提供了各种算法题目,...
【标题】"POJ1083-Moving Tables"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目主要考察的是算法设计和问题解决能力,通常在ACM/ICPC(国际大学生程序设计竞赛...
标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...
标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...
标题"Poj_1102_.rar_poj11"暗示了这是一个关于解决Poj_1102问题的资源包,通常在编程竞赛或在线判题系统如POJ(Problem Set of Judge Online)上遇到。POJ是中国的一个在线编程训练平台,提供了各种算法题目供用户...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
2遍dp poj_3613解题报告 poj_3613解题报告
【标题】"poj_3310.rar_3310_poj"是一个与编程竞赛相关的压缩包,其中包含了对POJ(Problem Online Judge)3310问题的解决方案和详细解析。POJ是一个著名的在线编程竞赛平台,提供各种算法题目供参赛者练习和提交...
标题 "ACM.zip_ACM_poj_poj3187_poj3669" 提供的信息表明,这个压缩包包含的是与ACM(国际大学生程序设计竞赛)相关的编程题目解决方案,具体是POJ(Programming Online Judge)平台上的两道题目,编号分别为poj3187...
《POJ 1010 Stamps:解题思路与陷阱分析》 POJ 1010,也被称为“邮票问题”,是编程竞赛中的一道经典题目,旨在考察参赛者的动态规划和数学思维能力。这个题目在编程爱好者中具有较高的知名度,因为它涉及到有趣的...
标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...
【标题】"poj_1002_487.rar_poj 1002"指的是北京大学在线编程平台上的第1002道题目,这道题目涉及到计算机科学中的算法设计与实现,特别是字符串处理和哈希映射。在这个问题中,我们需要编写一个程序,该程序能够...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
C_(POJ_1854)(分治).cpp
《POJ 1990:树状数组解题策略详解》 在编程竞赛的世界里,POJ(Programming Online Judge)是一个备受瞩目的在线评测系统,它提供了丰富的编程题目供参赛者挑战。其中,编号为1990的题目是一道涉及数据结构与算法...
D_(POJ_1723)(思维)(sort).cpp
D_(POJ_1723)(思维)(第k大数).cpp
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
标题“POJ_keptsl6_C++_”表明这是一个关于编程竞赛(POT, Problem Set of Judges)的资源,特别关注C++语言的解决方案。这些竞赛通常涉及到算法设计和实现,以解决各种计算机科学问题。"keptsl6"可能是用户特定的标记...
【标题】"poj_cpp.zip_MS_292AC_" 提示我们这是一份与POJ(编程在线判题系统)相关的压缩包,主要包含C++语言的解答,且可能涉及了MS(Microsoft)和292AC这两个特定的关键词。在POJ平台上,"MS_292AC_"可能是某个...