[NOIP2015 普及组] 推销员
题目背景
NOIP2015 普及组 T4
题目描述
阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。
螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。
螺丝街一共有 N 家住户，第 i 家住户到入口的距离为 Si 米。
由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。
阿明会从入口进入，依次向螺丝街的 X 家住户推销产品，然后再原路走出去。
阿明每走 1 米就会积累 1 点疲劳值，向第 i 家住户推销产品会积累 Ai 点疲劳值。
阿明是工作狂，他想知道，对于不同的 X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。
输入格式
第一行有一个正整数 N，表示螺丝街住户的数量。
接下来的一行有 N 个正整数，其中第 i 个整数 Si 表示第 i 家住户到入口的距离。数据保证S1≤S2≤…≤Sn<1e8。
接下来的一行有 N 个正整数，其中第 i 个整数 Ai 表示向第 i 户住户推销产品会积累的疲劳值。数据保证Ai<1e3。
输出格式
输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。
样例 #1
样例输入 #1
5
1 2 3 4 5
1 2 3 4 5
样例输出 #1
15
19
22
24
25
样例 #2
样例输入 #2
5
1 2 2 4 5
5 4 3 4 1
样例输出 #2
12
17
21
24
27
普及题,好像贪心能写, 线段树写法待补
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <climits>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define X first
#define Y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
struct P
{
int s, a;
} p[N];
int n;
int suma[N];
int maxs[N];
int t[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].s;
for (int i = 1; i <= n; i++)
cin >> p[i].a;
sort(p + 1, p + 1 + n, [&](P a, P b)
{if (a.a == b.a) return a.s > b.s;
return a.a > b.a; });
// for (int i = 1; i <= n; i++)
// cout << p[i].s << " " << p[i].a << endl;
for (int i = 1; i <= n; i++)
suma[i] = suma[i - 1] + p[i].a;
for (int i = 1; i <= n; i++)
maxs[i] = max(maxs[i - 1], p[i].s);
for (int i = n; i; i--)
t[i] = max(t[i + 1], p[i].s * 2 + p[i].a);
for (int i = 1; i <= n; i++)
{
cout << max(2 * maxs[i] + suma[i], suma[i - 1] + t[i]) << endl;
}
}
signed main()
{
FAST;
// cin >> T;
T = 1;
while (T--)
solve();
return 0;
}