洛谷P2672 推销员 题解 贪心

题目链接：https://www.luogu.org/problem/P2672

这道题目是贪心，贪心的思想是：

选择 \(m\) 户人家的最大疲劳值应该是以下两种方案中的较大值：

• 方案一：选择 \(a[i]\) 最大的 \(m\) 户人家；
• 方案二：选择 \(a[i]\) 最大的 \(m-1\) 户人家，以及剩下的 \(n-(m-1)\) 户人家中 \(2 \times s[i] + a[i]\) 最大的那户人家

所以，我们可以给 \(n\) 户人家按照 \(a[i]\) 从大到小金星排序。

然后在开三个数组（这3个数组用到了DP来进行求解）：

• suma[i] ：表示 \(\sum_{j=1}^{i}a[j] + 2 \times \max_{j=1}^{i}(s[j])\) ，推导公式： suma[i] = suma[i-1] + a[i]
• maxs[i] ：表示 \(\max_{j=1}^{i} s[j]\) ，推导公式： maxs[i] = maxs[i-1] + s[i]
• maxsa[i] ：表示 \(\max_{j=i}^{n} (2 \times s[j] + a[j])\) ，推导公式：maxsa[i] = max(maxsa[i+1], 2 \times s[i] + a[i])

然后我们要在 \(n\) 户人家里面选择 \(m\) 户人家访问的最大疲劳值就是 sum[m] + 2 * maxs[m] 和 suma[m-1] + 2 * maxs[i] 的较大值。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100100;

int n, s[maxn], a[maxn], idx[maxn], suma[maxn], maxs[maxn], maxsa[maxn];

bool cmp(int i, int j) {

    return a[i] > a[j];

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i ++) cin >> s[i];

    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++) idx[i] = i;

    sort(idx+1, idx+1+n, cmp);

    for (int i = 1; i <= n; i ++)

        suma[i] = suma[i-1] + a[idx[i]], maxs[i] = max(maxs[i-1], s[idx[i]]);

    for (int i = n; i >= 1; i --)

        maxsa[i] = max(maxsa[i+1], s[idx[i]] * 2 + a[idx[i]]);

    for (int i = 1; i <= n; i ++)

        cout << max(suma[i]+2*maxs[i], suma[i-1]+maxsa[i]) << endl;

    return 0;

}