首页 > 代码库 > UVa 11389 - The Bus Driver Problem

UVa 11389 - The Bus Driver Problem

题目:有n个上午的任务和下午的任务,分配给司机,如果工作总时间超过d,超过的部分要给加班费;

            现在让你安排任务,问最小的加班分花费。

分析:贪心。将两个任务分别按递增和递减序排序,每个对应边号的一组即可。

            设序列中的两组配对的元素为m1,a1,m2,a2 且 m1≤m2,a1≤a2;

            则配对方式<m1,a2>,<m2,a1>优于<m1,a1>,<m2,a2>(浪费的可能更少)。

说明:(⊙_⊙)。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int morni[101];
int after[101];

int cmp1(int a, int b){ return a < b; }
int cmp2(int a, int b){ return a > b; }

int main()
{
	int n,d,r;
	while (~scanf("%d%d%d",&n,&d,&r) && n) {
		for (int i = 0 ; i < n ; ++ i)
			scanf("%d",&morni[i]);
		for (int i = 0 ; i < n ; ++ i)
			scanf("%d",&after[i]);
		sort(morni, morni+n, cmp1);
		sort(after, after+n, cmp2);
		int sum = 0;
		for (int i = 0 ; i < n ; ++ i) 
			if (morni[i]+after[i] > d)
				sum += r*(morni[i]+after[i]-d);
		
		printf("%d\n",sum);
	} 
    return 0;
}


UVa 11389 - The Bus Driver Problem