算法
(贪心,前缀和) $O(n)$
这道题目的核心是发现如下性质:
向 $x$ 家住户推销产品的最大花费只有两种情况:推销给 $A_i$ 最大的 $x$ 家;或者推销给 $A_{i}$ 最大的 $x-1$ 家,然后最后一家尽可能远。
因此可以先将所有住户按 $A_i$ 从大到小排序。然后利用前缀和思想预处理出余下三个数组:
f[i]
表示前i
个 $A_i$ 的和;g[i]
表示前i
个 $S_i$ 的最大值;h[i]
表示i~n
中 $2S_i + A_i$ 的最大值;
那么向 $x$ 家住户推销产品的最大花费就是下面两种情况的最大值:
- 推销给 $A_i$ 最大的 $x$ 家:
f[i] + 2 * g[i]
- 推销给 $A_{i}$ 最大的 $x-1$ 家,然后最后一家尽可能远:
f[i - 1] + h[i]
时间复杂度
预处理前缀和数组和求每个 $x$ 对应的最大花费都是线性的,再加上排序,总时间复杂度是 $O(nlogn)$。
参考文献
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
PII w[N];
int f[N]; // 表示前i个a的和
int g[N]; // 表示前i个s的最大值
int h[N]; // 表示i~n中2s + a的最大值
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i].second);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i].first);
sort(w + 1, w + n + 1);
reverse(w + 1, w + n + 1);
for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] + w[i].first;
for (int i = 1; i <= n; i ++ ) g[i] = max(g[i - 1], w[i].second);
for (int i = n; i; i -- ) h[i] = max(h[i + 1], 2 * w[i].second + w[i].first);
for (int i = 1; i <= n; i ++ ) printf("%d\n", max(f[i] + 2 * g[i], f[i - 1] + h[i]));
return 0;
}
有两个疑问。
一:时间复杂度。感觉应该是O(NlogN)。除了构建数组,还要排序。这里时间复杂度取大的,就应该是排序的复杂度。
二: g[i]表示前i个 Si 最大值。您这里写的是 “g[i]表示前i个 Si 的和” 。可能是笔误。
/(ㄒoㄒ)/~~
多谢指正,已修正~
orz