[无来源]业务办理

发表于 2016-11-14   |   分类于 贪心  |  访问: 41 次


【问题描述】
在银行柜台前,有 n 个顾客排队办理业务。
队伍中从前往后,第 i 位顾客办理业务需要 ti分钟时间。
一位顾客的等待时间定义为:队伍中在他之前的所有顾客和他自己的办理业务 时间的总和。
第 i 位顾客有一个最长等待时间 di,如果超过了时间 di,业务还没有办理完成, 那么这位顾客就会觉得不满意。
具体来说,假设第 i 位顾客的等待时间为 fi,若 fi > di,则这 位顾客的不满意度为 fi-di,否则不满意度为 0。
你作为银行里的职员,需要安排这 n 位顾客的初始排队顺序,使得不满意度最大的那位 顾客不满意度最小。
【输入】
输入的第 1 行包含一个正整数 n,表示顾客的数量。
输入的第 2 行包含 n 个正整数,第 i 个数表示 ti,单位为分钟。
输入的第 3 行包含 n 个正整数,第 i 个数表示 di,单位为分钟。
【输出】
输出包含 1 个整数,表示最大不满意度的最小值。
【输入样例】
3
5 8 10
11 15 13
【输出样例】
8
【输入输出样例说明】
排队顺序 1 3 2
业务办理时间 5 10 8
等待时间 5 15 23
最长等待时间 11 13 15
不满意度 0 2 8
最大不满意度为 8。
这是最大不满意度能达到的最小值。
【数据规模与约定】
对于 50%的数据,n≤10
对于 70%的数据,n≤1,000
对于 100%的数据,n≤100,000,1≤ti≤104,0≤di≤10

看了标程的我来证明一下标程的做法:

假设已经排列出了最优的一种方案使得最大的等待时间最小化为k

再设等待时间最长的那个位置为x

则当d[i]<d[x]时,i不可能在x后面,因为这样i的等待时间势必会大于k

对于每个i都如此,所以正解就是按照等待时间d为关键字进行排序

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int _maxn=100001;
struct e{
	int t,d;
}a[_maxn];
bool cmp(e x,e y){
	return x.d<y.d;
}
int main(){
	freopen("transact.in","r",stdin);
	freopen("transact.out","w",stdout);
	int n,sum=0,x,y,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].t);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		a[i].d=x;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(sum+a[i].d>ans)
			ans=sum+a[i].d;
		sum+=a[i].t;
	}
	printf("%d\n",ans);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark