题解：P14336 [JOI2020 预选赛 R2] 草莓 / Strawberry

hyc42_Happiness · 2025-10-29 16:01:30 · 题解

前置

传送门

AC 记录

题意

有 N 个草莓 i（1\le i\le N）位于地点 A_i，并在时刻 T_i 成熟。

求将所有草莓均成熟且全摘完后，返回入口所需的最短时间。

思路

一个有意思的贪心。

最远的草莓决定了往返距离，也就是 2\times \max_{i=1}^{N}A_i

对于每个草莓，如果我们等到它成熟再去采摘，那么最早能在 T_i 时刻到达位置 A_i，此时总时间至少为 T_i+A_i（到达时间加上返回时间）。

所以最短时间就是 \max_{i=1}^{N}\max(2\times A_i,T_i+A_i)

Code

void solve(){
    cin>>n;
    while(n--){
        cin>>a>>b;
        maxn=max({maxn,2*a,a+b});
    }
    cout<<maxn;
    return;
}