1 条题解

  • 0
    @ 2023-7-12 23:44:45
    //按疲劳值a排序
    //要么取最大疲劳值的i个用户  + 其中的最大距离
    //要么取最大疲劳值的i-1个用户+(后面疲劳加距离综合最大的元素)
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int sum[100005];//疲劳前缀和
    int mju[100005];//前i个中的最大距离
    int mzh[100005];//后i个中疲劳+距离综合最大值
    
    struct node{
        int s,a;
    }f[100005];
    
    bool cmp1(node x,node y)
    {
        return x.a>y.a;
    }
    
    int main(){
        freopen("salesman.in","r",stdin);
        freopen("salesman.out","w",stdout);
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",&f[i].s);
        for(int i=1;i<=n;i++)scanf("%d",&f[i].a);
        sort(f+1,f+1+n,cmp1);
        
        for(int i=1;i<=n;i++)    
            sum[i]=sum[i-1]+f[i].a;
        for(int i=1;i<=n;i++)
            mju[i]=max(mju[i-1], f[i].s*2);
        for(int i=n;i>=1;i--)
            mzh[i]=max(mzh[i+1], f[i].s*2 + f[i].a);
        
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",max(sum[i]+mju[i], sum[i-1]+mzh[i]));
        }
        
        return 0;
    }
    
    • 1

    信息

    ID
    647
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    16
    已通过
    2
    上传者