UVa11389 The Bus Driver Problem

I I U C O N L I N E C O N T E S T 2 0 0 8
Problem E: The Bus Driver Problem
Input: standard input Output: standard output

In a city there are n bus drivers. Also there are n morning bus routes & n afternoon bus routes with various lengths. Each driver is assigned one morning route & one evening route. For any driver, if his total route length for a day exceeds d, he has to be paid overtime for every hour after the first d hours at a flat r taka / hour. Your task is to assign one morning route & one evening route to each bus driver so that the total overtime amount that the authority has to pay is minimized.
Input
The first line of each test case has three integers n, d and r, as described above. In the second line, there are n space separated integers which are the lengths of the morning routes given in meters. Similarly the third line has n space separated integers denoting the evening route lengths. The lengths are positive integers less than or equal to 10000. The end of input is denoted by a case with three 0 s.
Output
For each test case, print the minimum possible overtime amount that the authority must pay.
Constraints
- 1 ≤ n ≤ 100 - 1 ≤ d ≤ 10000 - 1 ≤ r ≤ 5
Sample Input	Output for Sample Input
2 20 5 10 15 10 15 2 20 5 10 10 10 10 0 0 0	50 0

Problem setter: Mohammad Mahmudur Rahman

题解：刚做完田忌赛马，还以为此题又是很猥琐。。。不过是在想不出什么贪心策略，直接把早上的按升序排，晚上的按降序排，两者相加，对超过部分进行统计，最后计算出加班费。提交上去AC了。。。不过想想贪心策略确实是这样的。记得高中数学书上有证明过，叫做排序不等式，以下摘自维基百科

排序不等式是数学上的一条不等式。它可以推导出很多有名的不等式，例如算术几何平均不等式，柯西不等式，和切比雪夫总和不等式。它是说：

如果

$x_1 \le x_2 \le \cdots \le x_n$ ，和

$y_1 \le y_2 \le \cdots \le y_n$

是两组实数。而

$x_{\sigma(1)}, \ldots, x_{\sigma(n)}$

是 $x_1, \ldots , x_n$ 的一个排列。排序不等式指出

$x_1y_1 + \cdots + x_ny_n \ge x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \ge x_ny_1 + \cdots + x_1y_n$ 。

以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。与很多不等式不同，排序不等式不需限定 $x_i, \, y_i$ 的符号。

此题的贪心策略证明方法应该和上述排序不等式证明的思想差不多，具体怎么证明我也不知道。。。。

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAXN 105
 5 int a[MAXN],b[MAXN];
 6 int compare(const void*a,const void*b)
 7 {
 8     return *(int*)a-*(int*)b;
 9 }
10 int main(void)
11 {
12     int n,i,d,r;
13     long ans;
14     while(scanf("%d%d%d",&n,&d,&r)!=EOF)
15     {
16         if(n==0&&d==0&&r==0) break;
17         for(i=0; i<n; i++)
18             scanf("%d",&a[i]);
19         for(i=0;i<n;i++)
20             scanf("%d",&b[i]);
21         qsort(a,n,sizeof(a[0]),compare);
22         qsort(b,n,sizeof(b[0]),compare);
23         ans=0;
24         for(i=0;i<n;i++)
25         if(a[i]+b[n-i-1]>d)
26             ans+=a[i]+b[n-i-1]-d;
27         printf("%ld\n",ans*r);
28     }
29     return 0;
30 }