Luogu P2672 推销员

Description：

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第ii家住户到入口的距离为S_i米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累A_i点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

Analysis：

60分做法：
根据样例可以发现，第 X 个最优解一定包含第 X - 1个最优解，所以可以每一次都枚举每个点，如果当前枚举的点比之前的点距离近，则答案加上当前点的疲劳值，否则答案加上2×（当前点到上一个点的距离）+ 当前点的疲劳值，时间复杂度O(n^2)。
非常感谢洛谷一位大佬的超神题解
[看第一篇题解](https://www.luogu.org/problemnew/solution/P2672 “Solution”)
对于每个x，一定是选择(一个最大的s)+(x-1个最大的a)或者x个最大的a，可以使答案最优。
所以先把数组按照a排序（从大到小），我们用sum[i]表示a数组的前i项的和，maxs[i]表示s数组的前i项的最大值，maxa[i]表示a[i]+2s[i]后i项的最大值，对于每个x，它的答案就是max(sum[x]+2maxs[x],sum[x-1]+maxa[x])，即比较 { 从1 到 第 x 大的疲劳值和加上这 x 个里面最大的往返距离 } 和 { 从 第 i 到 n 个 a[i]+2*s[i] 里的最大值 加上 最大的x - 1个a } 的大小

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX_N = 100010;
struct house{
    int s,a;
    /*
    bool operator < (house H) const {
        return a > H.a;
    }
    */
}h[MAX_N];
bool cmp(house A,house B)
{
    return A.a > B.a;
}
int sum[MAX_N],maxs[MAX_N],maxa[MAX_N],n;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;++i)
    {
        scanf("%d",&h[i].s);
    }
    for(int i = 1;i <= n;++i)
    {
        scanf("%d",&h[i].a);
    }
    sort(h+1,h+1+n,cmp);
    for(int i = 1;i <= n;++i)
    {
        maxs[i] = max(maxs[i-1],h[i].s);
        sum[i] = sum[i-1] + h[i].a;
    }
    for(int i = n;i >= 1;--i)
    {
        maxa[i] = max(maxa[i+1], 2*h[i].s + h[i].a);
    }
    for(int i = 1;i <= n;++i)
    {
        printf("%d
",max(sum[i] + 2*maxs[i],sum[i-1] + maxa[i]));
    }
    return 0;
}