http://acm.hdu.edu.cn/showproblem.php?pid=1050


这个题我首先直接用的常规贪心,用的和那个尽可能看更多完整节目那种思路。但是。。。。。。。一直WA。。。。T_T。。。。
后来在网上搜了一下这个题,发现好多人都有问题,都没有求出来,基本上都用的对尾部排序求的方法。
其实这个题因为是两排房间,所以1和2公用一个走廊,其中一个在需要移动的时候宁外一个还是不能移动。
所以我后面改了思路,直接改成了用两次排序直接找里面重叠部分最多的。(尾部排序的时候也要处理走廊的问题。)

AC了的代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; struct Node
{
int s,t;
int p;
} a[210]; bool cmp(Node a, Node b)
{
return a.t < b.t;
} int main()
{
int t,n,i,j,tim,ma;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i = 0; i < n; i++)
{
a[i].p = 0;
scanf("%d%d",&a[i].s,&a[i].t);
a[i].s = (a[i].s + 1) / 2; //处理奇偶公用一个走量的情况(这个一直没考虑,所以WA)
a[i].t = (a[i].t + 1) / 2;
if(a[i].s > a[i].t) //保证 s < t
{
j = a[i].s;
a[i].s = a[i].t;
a[i].t = j;
}
}
sort(a,a+n,cmp);
ma = 0;
for(i = 0; i < n; i++)
{
tim = 1;
for(j = i+1; j < n; j++)
{
if(a[j].s <= a[i].t)//判断是否有重叠
{
tim++; //增加一个重叠
}
}
if(tim > ma)
{
ma = tim;
}
}
printf("%d\n",ma*10);
} return 0;
}

最新文章

  1. C++ Template之类模版
  2. 关于何时view.setLayoutParams(params);
  3. 函数 MultiByteToWideChar() 详解
  4. LeeCode-Happy Number
  5. OpenSuSE zypper repo及Desktop媒体播放器设置 for OpenSuSE12.
  6. C#编码好习惯,献给所有热爱c#的同学
  7. 第二部分 职责型模式responsibility
  8. Android客户端连接服务器端,向服务器端发送请求HttpURLConnection
  9. dij洛谷电车
  10. Vagrant上运行SITL
  11. web页面简单布局的修改,测试中的应用
  12. this练习题
  13. POJ 1386 Play on Words (有向图欧拉路径判定)
  14. Linux的命名空间详解--Linux进程的管理与调度(二)
  15. 第二章 mybatis使用注解实现in查询(mysql)
  16. 如何搭建Spring MVC 框架---Hello World
  17. golang之交叉编译设置
  18. Python—XML
  19. 开发微信小程序入门前
  20. SQLServer添加链接服务器

热门文章

  1. Mybatis bug修正
  2. Storm技术结合
  3. Eclipse 安装Activiti 插件失败解决方法
  4. http://blog.csdn.net/bluejoe2000/article/details/39521405#t9
  5. 优化 Android 线程和后台任务开发
  6. 测试ODBC与OLE
  7. WordPress Pretty Photo插件‘hashrel’参数跨站脚本漏洞
  8. 【转】 Xcode基本操作 -- 不错
  9. CORREL
  10. android手机屏幕分辨率 及 sp dip(dp) px 区别 及高中低分辨率时处理