Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final) C. The Delivery Dilemma (贪心,结构体排序)

题意:你要买\(n\)份午饭,你可以选择自己去买,或者叫外卖,每份午饭\(i\)自己去买需要消耗时间\(b_i\),叫外卖需要\(a_i\),外卖可以同时送,自己只能买完一份后回家再去买下一份,问最少花多少时间能使午餐到家.
题解:我们可以用结构体记录每份午餐的外卖所需时间和自己拿的时间,然后贪心,对于某一份午餐,如果我们选择用外卖送,那么所有\(a_i\)比这个外卖时间小的在这个外卖送到时必然都能送到,所以我们可以对外卖时间进行排序,然后枚举每份午餐,每次让枚举位置和之前的位置用外卖送,枚举位置之后的自己跑去买,所以我们可以用后缀和记录自己买的时间,在外卖送的时间和自己买的时间之和之间取个最小值维护答案即可.

代码:

struct misaka{

    ll a,b;

    bool operator < (const misaka & mikoto) const{

        if(a!=mikoto.a) return a<mikoto.a;

        return b<mikoto.b;

    }

}e[N];

int t;

int n;

ll cnt[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

        cin>>n;

        for(int i=1;i<=n;++i) cin>>e[i].a;

        for(int i=1;i<=n;++i) cin>>e[i].b;

        sort(e+1,e+1+n);

        for(int i=n;i>=1;--i) cnt[i]=cnt[i+1]+e[i].b;

        ll ans=1e18;

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

            ans=min(ans,max(e[i].a,cnt[i+1]));

        }

        for(int i=1;i<=n;++i) cnt[i]=0;

        cout<<ans<<'\n';

    }

    return 0;

}

巴特西

Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final) C. The Delivery Dilemma (贪心,结构体排序)

最新文章

热门文章