題目描述
阿明是一名推銷員，他奉命到螺絲街推銷他們公司的産品。螺絲街是一條死胡同，出口與入口是同一個，街道的一側是圍牆，另一側是住戶。螺絲街一共有N家住戶，第i家住戶到入口的距離為Si米。由于同一棟房子裡可以有多家住戶，是以可能有多家住戶與入口的距離相等。阿明會從入口進入，依次向螺絲街的X家住戶推銷産品，然後再原路走出去。
阿明每走1米就會積累1點疲勞值，向第i家住戶推銷産品會積累Ai點疲勞值。阿明是工作狂，他想知道，對于不同的X，在不走多餘的路的前提下，他最多可以積累多少點疲勞值。
輸入格式
第一行有一個正整數N，表示螺絲街住戶的數量。
接下來的一行有N個正整數，其中第i個整數Si表示第i家住戶到入口的距離。資料保證S1≤S2≤...≤Sn＜10^8。
接下來的一行有N個正整數,其中第i個整數Ai表示向第i戶住戶推銷産品會積累的疲勞值。資料保證Ai＜10^3。
輸出格式
輸出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。
題解
容易想到，上次的最遠距離為$dis$時，這次的最遠距離$geqslant dis$。
此時選取有兩種情況：1.在滿足$s_{i} leqslant dis$的$a_{i}$中選取最大值；2.在滿足$a_{i} > dis$的$a_{i} + 2 imes (s_{i} - dis)$中選取最大值。
再加上之前積累的疲勞值即可。
因為$dis$隻會變大，是以情況1中的元素數量不會增多，我們可以排序一遍，然後每次選取沒被删除的最大值。情況2種元素數量會增加，是以我們可以用堆來維護。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 100000
using namespace std;
int n;
struct node {int dis, val, sum;}a[MAX_N];
priority_queue<int> q;
int pos, tval;
bool cmp(node a, node b)
{
if(a.sum != b.sum) return a.sum > b.sum;
return a.dis > b.dis;
}
void solve()
{
q.push(0);
for(int i = 0, iss = 1; i < n; i++)
{
if(iss) sort(a, a + n, cmp);
if(q.top() >= a[0].sum - pos * 2)
{
tval += q.top();
q.pop();
iss = 0;
}
else
{
tval += a[0].sum - pos * 2;
pos = a[0].dis;
iss = 1;
a[0].dis = a[0].val = a[0].sum = 0;
for(int j = 1; j < n; j++) if(a[j].dis && a[j].dis <= pos)
{
q.push(a[j].val);
a[j].dis = a[j].val = a[j].sum = 0;
}
}
if(i) putchar('
');
printf("%d", tval);
}
return;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i].dis);
for(int i = 0; i < n; i++) scanf("%d", &a[i].val);
for(int i = 0; i < n; i++) a[i].sum = a[i].dis * 2 + a[i].val;
solve();
return 0;
} 參考程式
但實際上，在洛谷上還有更優秀的做法，這裡發一下自己對那個做法的了解。
我們可以想，如果将所有的元素按照$a_{i} > a_{i + 1}$排序處理，那麼對于每個$x$，實際上解為：
$$max left { egin{matrix} underset {1 leqslant i leqslant x} {max} { s_{i} imes 2 } + sum_{i = 1}^{x} a_{i} (1)\ underset {x leqslant i leqslant n} {max} { a_{i} + s_{i} imes 2 }+ sum_{i = 1}^{x - 1} a_{i} (2) end{matrix}
ight.$$
其實也就是選擇最大的$x - 1$個$a_{i}$，再選擇第$x$大的$a_{i}$，或者選擇$a_{i}$更小但是$a_{i} + s_{i} imes 2$更大的。
有同學應該會認為$(2)$可能不成立。不要着急，繼續往下看。
容易想到，當$(1) leqslant (2)$時，因為$(2)$中選取的滿足$i geqslant x$的$a_{i}$顯然不大于$(1)$中的任何一個$a_{i}$，是以$(2)$中選取的$s_{i}$一定不小于$ underset {1 leqslant i leqslant x} {max} { s_{i} }$，是以此時$(2)$成立。
而當$(1) > (2)$時，同樣的，因為$(2)$中選取的滿足$i geqslant x$的$a_{i}$顯然不大于$(1)$中的任何一個$a_{i}$，是以$(2)$中選取的$s_{i}$可能不小于$ underset {1 leqslant i leqslant x} {max} { s_{i} }$，則此時$(2)$可能不成立。
當$(2)$不成立時，我們要讓$(2)$成立，則$(2)$的$s_{i}$也應選滿足$geqslant underset {1 leqslant i leqslant x} {max} {s_{i} }$。
但是，本身之前$(2)$在選取 $underset {x leqslant i leqslant n} {max} { a_{i} + s_{i} imes 2 }$，已經排除了$(2)$的$s_{i}$滿足$geqslant underset {1 leqslant i leqslant x} {max} {s_{i} }$的情況，是以即使改為$(2)$成立，也一定有$(1) > (2)$，那我們還管$(2)$幹什麼呢？（攤手）
是以直接這麼做就行了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N (100000 + 5)
using namespace std;
struct Node
{
int dis, val;
friend inline bool operator < (Node a, Node b)
{
return a.val > b.val;
}
};
int n;
Node a[MAX_N];
int s[MAX_N], md[MAX_N], p[MAX_N];
int main()
{
scanf("%d", &n);
for(register int i = 1; i <= n; ++i)
{
scanf("%d", &a[i].dis);
}
for(register int i = 1; i <= n; ++i)
{
scanf("%d", &a[i].val);
}
sort(a + 1, a + n + 1);
for(register int i = 1; i <= n; ++i)
{
s[i] = s[i - 1] + a[i].val;
md[i] = max(md[i - 1], a[i].dis);
}
for(register int i = n; i; --i)
{
p[i] = max(p[i + 1], a[i].val + a[i].dis * 2);
}
for(register int i = 1; i <= n; ++i)
{
printf("%d
", max(s[i] + md[i] * 2, s[i - 1] + p[i]));
}
return 0;
} 參考程式（更優）