首页 > 代码库 > hdu 4883 区间选点

hdu 4883 区间选点

昨天比赛的时候没有做出来,本来是想用贪心的,但是贪了好久都没有招,

今天在网上搜了解题报告~好像说这是一类区间选点问题:

有一个好的做法:

(1)首先把题目中的时间全转化为分钟,那么区间就在0-1440中间

 (2)对于n组人,有一个si 和一个ei,那么开个数组, cnt[si]+=d;  cnt[ei]-=d;

  ( 3 ) 也就是说在数轴上讲到达的这点加上d,离开的这点减去d;

附上代码

#include <iostream>
#include <cstdio>
#include <stdio.h>
using namespace std;
int cnt[1445];


int main()
{
 int t,n,d,s1,e1,s2,e2;
 cin>>t;
 while(t--)
 {
   cin>>n;
   memset(cnt,0,sizeof(cnt));
   for(int i=0;i<n;i++)
   {
     scanf("%d%d:%d%d:%d",&d,&s1,&e1,&s2,&e2);
     s1=s1*60+e1;
     s2=s2*60+e2;
     cnt[s1]+=d;
     cnt[s2]-=d;  
   }
   int sum=0,ans=0;
   for(int i=0;i<=1440;i++)
   {
     sum+=cnt[i];
     if(sum>ans)ans=sum;  
   }
   cout<<ans<<endl;
 }
 return 0;   
}