清北学堂模拟day4 业务办理

【问题描述】
在银行柜台前，有 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 = ;

struct dat{

    int t;

    int d;

};

int n;

ll ans,sumt;

dat orz[maxn];

int read(){

    char ch=getchar();

    int x=,f=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');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 = ;i <= n;i++) orz[i].t = read();

    for(int i = ;i <= n;i++) orz[i].d = read();

    sort(orz+,orz++n,cmp);

    ans = ;

    for(int i = ;i <= n;i++){

        sumt += orz[i].t;

        if(orz[i].d < sumt) ans = max(ans,sumt-orz[i].d);

    }

    cout<<ans;

    return ;

}