hdu 1050 Moving Tables

时间:2021-10-19 06:57:50

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;
}