luogu3550 [POI2013]TAK-Taxis

记一道不错的贪心。

地址：luogu2550

粘过来有乱码就不粘了。

第一眼的感觉肯定是贪心，因为人在还没过车站的时候离车站越远越不划算，浪费的路程也就越多，所以要尽量先叫行驶路程远的车

但是这样只能得50分。

比如说这组数据：

12 4 5
2 3 4 5 8

如果贪心的话显然是回不去的，为什么呢？

我们观察，当人过了车站之后，只需要一辆能从车站到家的车就够了，你有再多其他的车路程短也没用

所以贪心之前需要给自己留一个路程最小的能从车站回家的车，这个车之前不能用。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
long long inline read()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long m,d,n,a[500010];
bool comp(long long a,long long b)
{
    return a>b;
}
void cut(){puts("0");exit(0);}
main()
{
    m=read(),d=read(),n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+1+n,comp);
    long long res;
    for (res=1;res<=n;res++)
        if (a[res]<m-d)
            break;
    res--;if (!res) cut();
    long long now=0,ans=1;
    for (int i=1;i<=n;i++)
    {
        if(i==res)
            continue;
        if(now>=d || m-now+d-now<=a[res])
            break;
        if(a[i]<=d-now)
            cut();
        ans++;
        now+=a[i]-(d-now);
        if(now>=m)
        {
            ans--;break;
        }
    }
    if (m-now+d-now>a[res])
        puts("0");
    else
        printf("%d\n",ans);
}