[洛谷P3550][POI2013]TAK-Taxis

题目大意：一条路上有三个点，$0$为起始位置，$d$为总部，$m$为家。有$n$辆车，每辆车最多行驶$x_i$，都从$d$出发，可以在任意位置结束，问最少几辆车可以到家。

题解：贪心，发现当人在$[0,d)$时，车子越多，越浪费，所以尽可能用距离远的车。但这样也有可能导致最后没有车子从$d->m$，所以再最开始留下一辆可以的车。

注意判断只需要最后一辆车可以带到$m$，就可以结束循环，还有若无解，输出$0$，而非$-1$

卡点：无解输出了$-1$，应为$0$

 

C++ Code：

#include <algorithm>
#include <cstdio>
#include <vector>
#define maxn 500010

int n, ans;
long long m, d, x;
std::vector<long long> s;
int main() {
	scanf("%lld%lld%d", &m, &d, &n);
	for (int i = 0; i < n; ++i) {
		scanf("%lld", &x);
		s.push_back(x);
	}
	std::sort(s.begin(), s.end());
	long long a = 0;
	if (m - d) {
		int p = std::lower_bound(s.begin(), s.end(), m - d) - s.begin();
		if (p >= n) {
			puts("0");
			return 0;
		}
		a = s[p];
		s.erase(s.begin() + p);
	}
	std::reverse(s.begin(), s.end());
	long long pos = 0, td = d - (a - m + d >> 1);
	for (long long i : s) {
		long long t = i - d + pos;
		if (t <= 0) {
			puts("0");
			return 0;
		}
		pos += t;
		++ans;
		if (pos >= td) break;
	}
	printf("%d\n", ans + (pos < m));
	return 0;
}