UVA 1153 - Keep the Customer Satisfied

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;

   }

}