P3550 [POI 2013] TAK-Taxis

P3550 [POI 2013] TAK-Taxis

题目描述

Byteasar 想从 Bytehole 镇乘坐出租车前往 Bytepit 镇，两镇之间的距离为 $m$ 公里。

在从 Bytehole 镇前往 Bytepit 镇的途中，距离 Bytehole 镇恰好 $d$ 公里处，有一个停有 $n$ 辆出租车的基地，这些出租车编号为 1 到 $n$。

其中，第 $i$ 辆出租车的燃油量足够行驶恰好 $x_i$ 公里。

Byteasar 可以在任意地点换乘出租车。

所有出租车均从基地出发，且无需返回基地。

你的任务是判断 Byteasar 能否从 Bytehole 镇抵达 Bytepit 镇；若能抵达，求出完成这段行程所需的最少出租车数量。

输入格式

标准输入的第一行包含三个整数 $m$、$d$、$n$（$1 \le d \le m \le 10^{18}$，$1 \le n \le 500000$），整数之间用单个空格分隔。

它们分别表示：Bytehole 镇到 Bytepit 镇的距离、Bytehole 镇到出租车基地的距离、基地内出租车的数量。

输入的第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$（$1 \le x_i \le 10^{18}$），整数之间用单个空格分隔。

其中 $x_i$ 表示第 $i$ 辆出租车最多能行驶的距离（单位：公里）。

输出格式

你的程序应向标准输出打印一个整数：

即 Byteasar 从 Bytehole 镇到 Bytepit 镇所需的最少出租车数量。若无法抵达，则输出 $0$。

提示：此题需开 long long

---

分析：这道题其实是一道贪心的题，但不能直接叫最大的，因为。。。
eg：m=80,d=20,n=4,a1=75,a2=10,a3=30,a4=34。
如果直接叫75，就到不了家因为没有车可以从20到35，Byteasar就回不了家了。。。
所以，要先找到一辆可以从车站到家的车，然后再贪心。
代码如下：

#include
using namespace std;
#define int long long
int m,d,n,cnt,xz,ans=0;
int a[500005];
int cmp(int a,int b){
    return a>b;
}
signed main(){
    cin>>m>>d>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
    sort(a+1,a+1+n,cmp);//排序
    for(cnt=1;cnt<=n;cnt++){
    	if(a[cnt]break;	
		}
	}
    cnt--;
	if(cnt==0){
		cout<<"0";
		return 0;
	}
    for (int i=1;i<=n;i++){
        if(i==cnt){
        	continue;	
		}
        if(xz>=d||m+d-2*xz<=a[cnt]){
        	break;	
		}
        if(a[i]<=d-xz){
        	cout<<"0";
        	return 0;
		}
        ans++;
        xz+=a[i]-d+xz;
        if(xz>=m) {
            ans--;
			break;
        }
    }
    if(m+d-2*xz>a[cnt])cout<<"0";
    else cout<1;
    return 0;
}//AC