[POI2013]Taksówki

[POI2013]Taksówki

题目大意：

ABC三地在同一条直线上，AC相距(m(mle10^{18}))米，AB相距(d)，B在AC之间。总共有(n(nle5 imes10^5))辆车，每辆车只能从B地出发开(x_i)米（开完以后不必把车开回B地），问从A到C至少要坐几辆车？

思路：

对于BC之间的那一段路，如果可以走，则只要坐一辆车。对于AB之间的情况，只需要从大到小贪心即可。

将(x)排序后，找到大于等于(m-d)的最小的(x_i)，作为从B到C的车，剩下的车用来贪心。

时间复杂度(mathcal O(nlog n))。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<functional>
typedef long long int64;
inline int64 getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int64 x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=5e5;
int64 x[N];
int main() {
	const int64 m=getint(),d=getint();
	const int n=getint();
	for(register int i=0;i<n;i++) x[i]=getint();
	std::sort(&x[0],&x[n],std::greater<int64>());
	if(x[0]<m-d) {
		puts("0");
		return 0;
	}
	int i,k;
	for(k=0;k+1<n&&x[k+1]>=m-d;k++);
	int64 p;
	for(p=i=0;i<n&&p+x[k]-std::max(d-p,0ll)<m&&x[i]>=d-p;i++) {
		if(i!=k) p+=x[i]-d+p;
	}
	if(i<=k) i++;
	if(p>=m) {
		printf("%d
",i-1);
		return 0;
	}
	printf("%d
",p+x[k]-std::max(d-p,0ll)>=m?i:0);
	return 0;
}