阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有N家住户,第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的X家住户推销产品,然后再原路走出去。
阿明每走1米就会积累1点疲劳值,向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂,他想知道,对于不同的X,在不走多余的路的前提下,他最多可以积累多少点疲劳值。
阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有N家住户,第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的X家住户推销产品,然后再原路走出去。
阿明每走1米就会积累1点疲劳值,向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂,他想知道,对于不同的X,在不走多余的路的前提下,他最多可以积累多少点疲劳值。
第一行有一个正整数N,表示螺丝街住户的数量。
接下来的一行有N个正整数,其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn<108。
接下来的一行有N个正整数,其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<103。
输出N行,每行一个正整数,第i行整数表示当X=i时,阿明最多积累的疲劳值。
5 1 2 3 4 5 1 2 3 4 5
15 19 22 24 25
X=1: 向住户5推销,往返走路的疲劳值为5+5,推销的疲劳值为5,总疲劳值为15。
X=2: 向住户4、5推销,往返走路的疲劳值为5+5,推销的疲劳值为4+5,总疲劳值为5+5+4+5=19。
X=3: 向住户3、4、5推销,往返走路的疲劳值为5+5,推销的疲劳值3+4+5,总疲劳值为5+5+3+4+5=22。
X=4: 向住户2、3、4、5推销,往返走路的疲劳值为5+5,推销的疲劳值2+3+4+5,总疲劳值5+5+2+3+4+5=24。
X=5: 向住户1、2、3、4、5推销,往返走路的疲劳值为5+5,推销的疲劳值1+2+3+4+5,总疲劳值5+5+1+2+3+4+5=25。
5 1 2 2 4 5 5 4 3 4 1
12 17 21 24 27
X=1:向住户4推销,往返走路的疲劳值为4+4,推销的疲劳值为4,总疲劳值4+4+4=12。
X=2:向住户1、4推销,往返走路的疲劳值为4+4,推销的疲劳值为5+4,总疲劳值4+4+5+4=17。
X=3:向住户1、2、4推销,往返走路的疲劳值为4+4,推销的疲劳值为5+4+4,总疲劳值4+4+5+4+4=21。
X=4:向住户1、2、3、4推销,往返走路的疲劳值为4+4,推销的疲劳值为5+4+3+4,总疲劳值4+4+5+4+3+4=24。或者向住户1、2、4、5推销,往返走路的疲劳值为5+5,推销的疲劳值为5+4+4+1,总疲劳值5+5+5+4+4+1=24。
X=5:向住户1、2、3、4、5推销,往返走路的疲劳值为5+5,推销的疲劳值为5+4+3+4+1,总疲劳值5+5+5+4+3+4+1=27。
对于20%的数据,1≤N≤20;
对于40%的数据,1≤N≤100;
对于60%的数据,1≤N≤1000;
对于100%的数据,1≤N≤100000。
n = int(input()) poi = [int(x) for x in input().split()] val = [int(x) for x in input().split()] # 最优策略:要找n户 # 1. 找到最大+最右(+编号最大)的n户,设为集合S。“折返点”不可能在“集合S最右边的点”的左侧。因为左侧说明poi*2不如“最右”大,大小又不如最大的n户大。 # 2. “折返点”可能在右侧,因此在坐标[集合S最右边的点, +inf]的点中,找到val+poi*2最大的点作为“折返点” # 3. 检查折返点是不是S中的点,不是的话,只能取S中的前n-1大的点+折返点 points = [(i, poi[i], val[i]) for i in range(n)] points_by_poi = sorted(points, key=lambda x: x[1]) get_return_point = {} # 闭区间,max val+poi*2 in [key, end] cur_max_point = (0, 0, float('-inf')) for i in reversed(range(n)): p = points_by_poi[i] update = False if (p[2] + p[1] * 2 > cur_max_point[2] + cur_max_point[1] * 2 or p[2] + p[1] * 2 == cur_max_point[2] + cur_max_point[1] * 2 and p[0] < cur_max_point[0]): update = True if update: cur_max_point = p get_return_point[p[1]] = cur_max_point points_by_val = sorted(points, key=lambda x: (x[2], x[1], x[0]), reverse=True) presum = [points_by_val[0][2]] for i in range(1, n): presum.append(presum[-1] + points_by_val[i][2]) cur_max = 0 rightest = [] for p in points_by_val: cur_max = max(cur_max, p[1]) rightest.append(cur_max) for i in range(n): # search return point in [start, end] start = rightest[i] return_point = get_return_point[start] if (return_point[1] == start and (points_by_poi[i][1] < start or points_by_poi[i][1] == start and points_by_poi[i][0] <= return_point[0])): # 折返点在集合S中 print(presum[i] + 2 * start) else: print(presum[i] - points_by_val[i][2] + return_point[2] + return_point[1] * 2)
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define For(i,s,t) for (int i = (s); i <= (t); ++i) #define rFor(i,t,s) for (int i = (t); i >= (s); --i) #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " " #define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a)) #define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int> #define piii pair<pair<int,int>,int> #define mp make_pair #define pb push_back #define fi first #define se second inline int gc(){ static const int BUF = 1e7; static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, 1, BUF, stdin); return *bg++; } inline int ri(){ int x = 0, f = 1, c = gc(); for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); return x*f; } typedef long long LL; const int maxN = 1e5 + 7; int n; int dist[maxN], cost[maxN]; int suffixMax[maxN]; //记录dist的后缀最大值 int f[maxN]; // f[i]表示当X=1时在1~i范围内只选择1家住户的最优解 int prefixSum[maxN]; // cost的前缀和 int getSum(int x, int y){ return x < y ? prefixSum[y] - prefixSum[x] : 0; } void mergeSort(int l, int r){ if(l >= r) return; int mid = (l+r) >> 1; mergeSort(l, mid); mergeSort(mid+1, r); int tmp1[r-l+1], tmp2[r-l+1]; int i = l, j = mid + 1, k = 0; while(i <= mid && j <= r){ if(cost[i] > cost[j] || cost[i] == cost[j] && dist[i] > dist[j]){ tmp1[k] = cost[j]; tmp2[k++] = dist[j++]; } else{ tmp1[k] = cost[i]; tmp2[k++] = dist[i++]; } } while(i <= mid){ tmp1[k] = cost[i]; tmp2[k++] = dist[i]; ++i; } while(j <= r){ tmp1[k] = cost[j]; tmp2[k++] = dist[j]; ++j; } rep(i, k){ cost[i+l] = tmp1[i]; dist[i+l] = tmp2[i]; } } int main(){ scanf("%d", &n); For(i, 1, n) dist[i] = ri(); For(i, 1, n) cost[i] = ri(); mergeSort(1, n); rFor(i, n, 1) suffixMax[i] = max(suffixMax[i+1], dist[i]); For(i, 1, n) f[i] = max(f[i-1], cost[i] + dist[i]*2); For(i, 1, n) prefixSum[i] = prefixSum[i-1] + cost[i]; rFor(i, n, 1) printf("%d\n", max(getSum(i, n) + f[i], getSum(i-1, n) + 2*suffixMax[i])); return 0; }