Luogu

算法

贪心。

考虑每次选一个路程最大的出租车,可以保证数量最小……吗?

考虑这种情况:你将路程大的全选了,然后没有车能送你到家了。

我觉得布星。

所以我们要留下一辆车能从车站送自己到家。这辆车应该是所有能从车站到家的车中$a$最小的。

那么贪心即可。注意很多细节(见代码)。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline bool cmp(const int& a,const int& b) {
    return a>b;
}

int s,m,n;
int a[500010];
    
mainint main() {
    n=read(),m=read(),s=read();
    for (re int i=1;i<=s;i++) a[i]=read();
    sort(a+1,a+s+1,cmp);
    int p=-1; //-1是全都可以的情况
    for (re int i=1;i<=s;i++)
        if (a[i]<n-m) { p=i-1; break; }
    if (!p) { puts("0"); return 0; }
    int now=0,ans=0;
    for (re int i=1;i<=s;i++) {
        if (i==p) continue; //留下的车不能动
        if (now>=m||n-now+m-now<=a[p]) break; //到车站了,或者留的车能送到了
        if (a[i]<=m-now) { puts("0"); return 0; } //这辆车带不了你,而且留的车还送不到家
        ans++; now+=a[i]-(m-now);
        if (now>=n) { printf("%lld\n",ans); return 0; } //直接到了
    }
    if (n-now+m-now>a[p]) puts("0");
    else printf("%lld\n",ans+1);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 18 PM