首页 > ACM题库 > HDU-杭电 > HDU 2972-Two professors[解题报告]HOJ
2014
02-24

HDU 2972-Two professors[解题报告]HOJ

Two professors

问题描述 :

There are two professors at the great Academy of X that really do not get along with each other. In order not to reveal their names, we will call them 1 and 2. The Academy employs exactly n professors; each of them has to give exactly one lecture. As their schedules are rather tight (they are professors,
remember?), the starting and the ending time of each lecture is already fixed. However, it is not yet fixed where each lecture will take place. Obviously, it is impossible to schedule two lectures in the same room if their durations overlap; on the other hand, it is possible if one of them starts exactly at the same time that the other one ends. Your tasks is to find the minimal number of rooms allowing to arrange all the lectures. But know that professors 1 and 2 hate each other so much that they will never give their lectures in the same room.

输入:

The input contains several test cases. The first line contains the number of test cases t (t <= 250). Each test begins with a line containing the number of professors n (2 <= n <= 10^5). Next n lines follow, i-th of which contains two integers starti and endi (0 <= starti < endi <= 10^9), the starting and the ending time of the lecture that the i-th professor gives, respectively. Total size of the input will not exceed 50MB.

输出:

The input contains several test cases. The first line contains the number of test cases t (t <= 250). Each test begins with a line containing the number of professors n (2 <= n <= 10^5). Next n lines follow, i-th of which contains two integers starti and endi (0 <= starti < endi <= 10^9), the starting and the ending time of the lecture that the i-th professor gives, respectively. Total size of the input will not exceed 50MB.

样例输入:

4
2
0 10
10 20
3
0 10
10 20
10 20
5
4 14
3 13
2 12
1 11
0 10
4
0 10
10 20
20 30
30 40

样例输出:

2
2
5
2

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct node
{
 int l,r,id,flag;
 bool operator < (const node &b) const
 {
 return r>b.r;
 }
};
priority_queue <node> q;
bool cmp(const node &a,const node &b)
{
 if (a.l!=b.l) return a.l<b.l;
 return a.id>b.id;
 //return a.r<b.r;
}
node a[100010];
int main()
{
 int T;

 //freopen("in.in","r",stdin);
 // freopen("out.out","w",stdout);
 scanf("%d",&T);
 while (T--)
 {
 int n;
 scanf("%d",&n);
 for (int i=0;i<n;i++)
 {
 scanf("%d%d",&a[i].l,&a[i].r);
 a[i].id=i+1;
 a[i].flag=0;
 }

 bool good=0;
 if (max(a[0].l,a[1].l)<min(a[0].r,a[1].r)) good=1;
 a[1].flag=1;
 a[0].flag=1;
 sort(a,a+n,cmp);
 while (!q.empty()) q.pop();

 int ans=0;
 int numa=0;
 int numb=0;
 int now=0;
 int bad=0;
 int maxs=0;
 for (int i=0;i<n;i++)
 {
 while(!q.empty()&&q.top().r<=a[i].l)
 {
 node s=q.top();
 q.pop();
 if (s.flag) numb++;
 else numa++;
 now--;
 }
// printf(" fisrt now=%d nowa=%d nowb=%d l=%d i=%d\n",
// now,numa,numb,a[i].l,i);
 if (bad!=1)
 {
 numa+=numb;
 numb=0;
 if (numa)
 {
 numa--;
 }
 } else
 {
 if (numa&&numb) good=1;
 if (numa)
 {
 numa--;
 if (a[i].flag) good=1;
 } else
 if (numb)
 {
 a[i].flag=1;
 numb--;
 } else
 if (a[i].flag) good=1;
 }

 q.push(a[i]);
 now++;
 if (a[i].id<=2) bad++;
// printf(" second now=%d nowa=%d nowb=%d l=%d i=%d good=%d\n\n",
// now,numa,numb,a[i].l,i,good);
 if (now+numa+numb>ans) ans=now+numa+numb;
 if (bad==1)
 if (now+numa+numb>maxs) maxs=now+numa+numb;
 }
 // printf("good=%d ",good);
 maxs+=!good;
 if (maxs>ans) ans=maxs;
 printf("%d\n",ans);
 }
 return 0;
}

  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。