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

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

CPP

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 数据，欢迎质疑。

CPP

#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;
}

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

文章操作

相关推荐

评论

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