【问题描述】
在银行柜台前，有 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 个整数，表示最大不满意度的最小值。
【输入输出样例 1】

transact.in transact.out
3
5 8 10
11 15 13		 8


见选手目录下的 transact / transact1.in 与 transact / transact1.out
【输入输出样例 1 说明】

排队顺序 1 3 2
业务办理时间 5 10 8
等待时间 5 15 23
最长等待时间 11 13 15
不满意度 0 2 8


最大不满意度为 8。 这是最大不满意度能达到的最小值。
【输入输出样例 2】
见选手目录下的 transact / transact2.in 与 transact / transact2.out
【数据规模与约定】
对于 50%的数据， n≤10
对于 70%的数据， n≤1,000
对于 100%的数据， n≤100,000， 1≤ti≤104， 0≤di≤109 

/*
贪心，直觉告诉我们d越大应该越往后
证明：当前序列，i<j则di<dj假设i取最大忍耐度，如果可以使这个忍耐度减小，使其与j互换
①j > i，对于i来说，则sumt要变大，一定不行
②j < i，对于j来说，dj < di，sumt不变，答案也要变大
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 100050;
struct dat{
    int t;
    int d;
};
int n;
ll ans,sumt;
dat orz[maxn];
int read(){
    char ch=getchar();
    int x=0,f=1;
    while(!(ch>=\'0\'&&ch<=\'9\')){if(ch==\'-\')f=-1;ch=getchar();};
    while(ch>=\'0\'&&ch<=\'9\'){x=x*10+(ch-\'0\');ch=getchar();};
    return x*f;
}
bool cmp(dat a,dat b){
    return a.d < b.d;
}
int main(){
    freopen("transact.in","r",stdin);
    freopen("transact.out","w",stdout);
    n = read();
    for(int i = 1;i <= n;i++) orz[i].t = read();
    for(int i = 1;i <= n;i++) orz[i].d = read();
    sort(orz+1,orz+1+n,cmp);
    ans = 0;
    for(int i = 1;i <= n;i++){
        sumt += orz[i].t;
        if(orz[i].d < sumt) ans = max(ans,sumt-orz[i].d);
    }
    cout<<ans;
    return 0;
}

 

 

版权声明：本文为hyfer原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/hyfer/p/5964620.html