[POI 20 Stage 1] Taxis

作法：

當那個人被載到超越了計程車停的地方時，就只需要一台計程車了，如果用了兩台才把他送到終點，那不如用之後那台一次就可以載到了，反正他們要跑的距離都固定。所以可以想到只要取 >= m - d 的耐力最小的計程車就夠了。剩下的就是直接貪心，從耐力最大的開始載，如果載不到計程車停的地方就是失敗。最後還要注意從計程車停的地方左邊直接被載到終點的可能性。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=500000+10 ;
 
LL m,d ; int n ;
LL a[maxn] ;
 
int solve()
{
    sort(a+1,a+n+1) ;
    if(a[n]<m-d) return 0 ;
    if(a[n]>=d+m) return 1 ;
 
    LL tmp ;
    for(int i=1;;i++) if(a[i]>=m-d)
    {
        tmp=a[i] ;
        for(int j=i;j<n;j++) a[j]=a[j+1] ;
        n-- ; break ;
    }
 
    int ans=1 ; LL now=0LL ;
    for(int i=n;i>=1;i--)
    {
        if(a[i]<=d-now) return 0 ;
        ans++ ; now+=a[i]-(d-now) ;
        if(now>=d) break ;
        if(2*(d-now)+m-d <= tmp) return ans ;
    }
    if(now<d) return 0 ;
    if(now>=m) return now>=m ? ans-1 : ans ;
}
 
main()
{
    scanf("%lld%lld%d",&m,&d,&n) ;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]) ;
    printf("%d\n",solve()) ;
}