luogu2672 推销员

题目描述

阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有$N$家住户,第$i$家住户到入口的距离为$S_i$米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的$X$家住户推销产品,然后再原路走出去。

阿明每走$1$米就会积累$1$点疲劳值,向第$i$家住户推销产品会积累$A_i$点疲劳值。阿明是工作狂,他想知道,对于不同的$X$,在不走多余的路的前提下,他最多可以积累多少点疲劳值。

输入格式

第一行有一个正整数$N$,表示螺丝街住户的数量。

接下来的一行有$N$个正整数,其中第$i$个整数$S_i$表示第$i$家住户到入口的距离。数据保证$S_1≤S_2≤…≤S_n<10^8$。

接下来的一行有$N$个正整数,其中第$i$个整数$A_i$表示向第$i$户住户推销产品会积累的疲劳值。数据保证$A_i<1000$。

输出格式

输出$N$行,每行一个正整数,第i行整数表示当$X=i$时,阿明最多积累的疲劳值。

样例输入

5
1 2 3 4 5
1 2 3 4 5

样例输出

15
19
22
24
25

说明

【数据说明】

对于$20\%$的数据,$1≤N≤20$;

对于$40\%$的数据,$1≤N≤100$;

对于$60\%$的数据,$1≤N≤1000$;

对于$100\%$的数据,$1≤N≤100000$。


分析

过了几年还是写不出这道普及组题……NOIP退役预定……

此题正解为贪心:每次选一个能使疲劳值增加最多的点。

写这篇题解主要是学习一下贪心的证明方法:

已知$X_n$为拜访$n$户的最优解,$X_n=(\sum_{i=1}^{n}a[p_i])+2\cdot s[p_n]$;$X_{n+1}$为拜访$n+1$户的最优解,$X_{n+1}=(\sum_{i=1}^{n+1}a[q_i])+2\cdot s[q_{n+1}]$。

我们要证明的是$X_{n+1}$的选择方案一定包含$X_n$。利用反证法,假设$X_{n+1}$不包含$X_n$。

分类讨论:

若$q_{n+1}\le p_n$,设$q_k$不在${p_1,p_2,\dots,p_n}$中,则:

$$ \begin{align} X_{n+1}&=(\sum_{i=1}^{n+1}a[q_i])+2\cdot s[q_{n+1}]\\ &\le(\sum_{i=1,i\not =k}^{n+1}a[q_i])+2\cdot s[p_n]+a[q_k]\\ &<X_n+a[q_k] \end{align} $$

那么在$X_n$的基础上选$q_k$一定比$X_{n+1}$优,矛盾。

若$q_{n+1}>p_n$,则: $$ \begin{align} X_{n+1}&=(\sum_{i=1}^{n+1}a[q_i])+2\cdot s[q_{n+1}]\\ &=(\sum_{i=1}^{n}a[q_i])+2\cdot s[p_n]+a[q_{n+1}]+2\cdot (s[q_{n+1}]-s[p_n])\\ &<X_n+a[q_{n+1}]+2\cdot (s[q_{n+1}]-s[p_n]) \end{align} $$

那么在$X_n$的基础上选$q_{n+1}$一定比$X_{n+1}$优,矛盾。

综上,$X_{n+1}$的选择方案一定包含$X_n$。那么显然每次都要选让疲劳值增加最多的点。

代码实现:开两个堆分别维护$a_i$与$a_i+2s_i$,复杂度$O(n\log n)$。

代码

#include <bits/stdc++.h>

const int N = 1e5+50;

struct Data {
    int val, pos;

    bool operator < (const Data &t) const {
        return val < t.val;
    }
};

int n, a[N], s[N];
std::priority_queue<int> ql;
std::priority_queue<Data> qr;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        qr.push((Data){a[i]+2*s[i], i});
    }
    int mx = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        int left = 0, right = 0;
        if (!ql.empty()) left = ql.top();
        while (!qr.empty() && qr.top().pos <= mx) qr.pop();
        if (!qr.empty()) right = qr.top().val;
        if (right - 2*s[mx] > left) {
            int pos = qr.top().pos; qr.pop();
            ans += right - 2*s[mx];
            for (int j = mx+1; j < pos; j++) {
                ql.push(a[j]);
            }
            mx = pos;
        } else {
            ans += left; ql.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论