UVa 11389 The Bus Driver Problem

題意：
    有n個司機，早班有n條路線，晚班也有n條路線，這2n條路線都有不同的距離，要安排每一個司機早班和晚班各一條路線，但是如果早班+晚班的路線距離超過d的話，超過每1單位就要加班費r元，求如何安排路線給每位司機使得全部加班費為最小，並輸出。

想法：
    將早班n條路線由小到大排序，晚班也是，為了使得加班費總和最少，安排時就要盡量填滿d，因此早班最短配上晚班最長路線，然後早班第二短配上晚班第二長,.....依此類推。如果最短配上最短，會導致該路線和遠小於d，表示浪費了這位司機還剩下的距離，因此要盡量讓每位司機平均填滿d。

	#include <cstdio>
	#include <algorithm>
	int main()
	{
	int n, d, r;
	int morning[105], night[105];
	while (scanf("%d %d %d", &n, &d, &r) && (n || d || r)) {
	for (int i = 0; i < n; ++i) scanf("%d", &morning[i]);
	for (int i = 0; i < n; ++i) scanf("%d", &night[i]);
	std::sort(morning, morning + n);
	std::sort(night, night + n);
	int fine = 0;
	for (int i = 0; i < n; ++i)
	if (morning[i] + night[n-i-1] > d)
	fine += ((morning[i] + night[n-i-1] - d) * r);
	printf("%d\n", fine);
	}
	}

view raw [UVa] 11389 The Bus Driver Problem.cpp hosted with ❤ by GitHub