2016年9月2日 星期五

UVA 1153 - Keep the Customer Satisfied


題目概述:經典入門書p8-49
time&deadline題。

思路:
gready。
先對deadline做排序。接著一個一個加入pq,若發現時間超過,則拿掉最pq.top()。
最後答案為pq.size()。

//By SCJ
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 10000000000000
struct P{
   double x1,x2;
}es[100001];
bool cmp(P a,P b)
{
   return a.x1<b.x1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
   double L,D;
   int n;
   while(cin>>L>>D>>n)
   {
       for(int i=0;i<n;++i)
       {
           double x,y;cin>>x>>y;
           double dx=sqrt(D*D-y*y);
           es[i]={x-dx,x+dx};
       }
       sort(es,es+n,cmp);
       double la=INF;
       int ans=0;
       for(int i=0;i<n;++i)
       {
           P e=es[i];
           if(e.x1>la) ans++,la=e.x2;
           else la=min(la,e.x2);
       }
       if(n==0) cout<<0<<endl;
       else cout<<ans+1<<endl;
   }
}

沒有留言:

張貼留言