【正经题解】推销员

考虑我们如何将答案最大化：对于每个x，一定是选择(一个最大的s)+(x-1个最大的a)或者x个最大的a，可以使答案最优

那么具体怎么实现呢

我们先把数组按照a排序

我们用sum[i]表示a数组的前i项的和，q[i]表示s数组的前i项的最大值，h[i]表示a[i]2+s[i]后i项的最大值，对于每个x，他的答案就是max(sum[x]+2q[x],sum[x-1]+h[x])

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct home{
    int s,v;
}a[100010];
int q[100010];
int h[100010],qm[100010];
int n;
bool cmp(home a,home b)
{
    return a.v>b.v;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].s);
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
    }
    sort(a+1,a+1+n,cmp);
    for (int i=n;i>=1;i--)
    {
        h[i]=max(h[i+1],2*a[i].s+a[i].v);
    }
    for (int i=1;i<=n;i++)
    {
        qm[i]=max(qm[i-1],a[i].s);
    }
    for (int i=1;i<=n;i++)
        q[i]=q[i-1]+a[i].v;
    for (int i=1;i<=n;i++)
    {
        printf("%d\n",max(q[i-1]+h[i],q[i]+2*qm[i]));
    }
}