题解：B4156 [厦门小学生 C++ 2023] 太空旅行

· · 题解

假如我们确定了顺序，我们计算总时间的方式应该是这样的。

int tmp=0,ans=0;
for(int i=1;i<=n;++i){
    tmp+=a[i].u;
    ans=max(ans,tmp)+a[i].v;
}cout<<ans<<'\n';

因为地球到火星是可以不停顿的，所以 tmp 可以一直加上，最终到天王星的时间取决与火星到天王星和地球到火星两个值，所以要取 \max。

那么我们可以通过这个计算方式考虑我们的贪心。对答案变化有影响的就是其中的 \max，我们将 u<v 和 u\ge v 的各分一组。由于最终 ans\ge sum(v) 不可逃避，我们只希望 tmp 不对 ans 造成过大的影响，所以优先让 u<v 的通过。同样 u<v 的选择 u 小的先通过。对于 u>v 的将 v 大的优先通过。

总感觉怪怪的，但是通过了洛谷的所有 hack 数据，欢迎质疑。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
const int N=25005,INF=1e9;
int n,tmp,ans;
vector<pii> v1,v2;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x,y;i<=n;++i)
        cin>>x>>y,x<y?v1.pb(mk(x,y)):v2.pb(mk(y,x));
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    reverse(v2.begin(),v2.end());
    for(auto v:v1)
        tmp+=v.first,ans=max(ans,tmp)+v.second;
    for(auto v:v2)
        tmp+=v.second,ans=max(ans,tmp)+v.first;
    cout<<ans<<'\n';
    return 0;
}