AC代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N=100010;
PII a[N];
int s[N]; //s[i]表示前i户Ai的和
int f[N]; //表示前i户Si的最大值
int g[N]; //表示i~n中2Si + Ai的最大值
int main()
{
    int n;
    scanf("%d",&n);//输入Si
    for(int i=1;i<=n;i++) scanf("%d",&a[i].second); //输入Ai
    for(int i=1;i<=n;i++) scanf("%d",&a[i].first); //按照Ai从大到小排序
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);//预处理s[i],表示前向前i家住户推销产品的疲劳值前缀和
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].first;//预处理f[i],表示从入口到前i家住户距离Si的最大值
    for(int i=1;i<=n;i++) f[i]=max(f[i-1],a[i].second);//预处理g[i],表示2 * Si + Ai的最大值
    //注意，这里从后向前计算, 先计算出小Ai值对应的g[i]
    //因为g[i]表示的是从i~n家2*Si +Ai最大值
    for(int i=n;i>=1;i--) g[i]=max(g[i+1],2*a[i].second+a[i].first);//输出
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",max(s[i]+2*f[i],s[i-1]+g[i]));
    }
    return 0;
}