M_sea

洛谷3550 [POI2013]TAK-Taxis
upd:开了个O2,跑到了最优解qwqupd2:被ych巨佬反超了qwqych太强啦题意有一条数轴,你在$0$,出...
扫描右侧二维码阅读全文
21
2018/08

洛谷3550 [POI2013]TAK-Taxis

upd:开了个O2,跑到了最优解qwq

upd2:被ych巨佬反超了qwqych太强啦

题意

有一条数轴,你在$0$,出租车站在$d$,你家在$m$。车站有$n$辆出租车,第$i$辆可以走$a[i]$个单位,不要求一定回到车站。

求你最少要坐几辆车才能到家。

传送门

算法

贪心。

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

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

$emmmmmm......$
我觉得布星。

所以我们要留下一辆车能从车站送自己到家。这辆车应该是所有能从车站到家的车中$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;
}
最后修改:2018 年 11 月 09 日 05 : 17 PM

发表评论

2 条评论

  1. Qihoo360

    不是最优解差评(逃

    1. M_sea
      @Qihoo360

      日常被嘲讽

      Orz