#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
long 住户[100001][2];
long 每个住户的值[100001], 临时总值[100001], 结果[100001];

int main(void) {

long 数量,i,j;
scanf("%ld", &数量);
for (i = 0;i < 数量;i++)
scanf("%ld", &住户[i][0]);//记录距离
for (i = 0;i < 数量;i++)
scanf("%ld", &住户[i][1]);//记录产品疲劳值
long 临时最大,当前最累住户=0;
for (i = 0;i < 数量;i++) {
临时总值[i] = 2*住户[i][0] + 住户[i][1];
if (临时总值[当前最累住户] < 临时总值[i])
当前最累住户 = i;

}
结果[0] = 临时总值[当前最累住户];
long temp;
for (i = 0;i < 数量;i++)
{
/* temp = 住户[当前最累住户][0] - 住户[i][0];
if (temp < 0)
临时总值[i]=2*abs(住户[当前最累住户][0] - 住户[i][0]);
else 临时总值[i] -= 住户[i][0];*/

if (i < 当前最累住户)
临时总值[i] -= 2 * 住户[i][0];
else
临时总值[i] += 2 * (住户[i][0] - 住户[当前最累住户][0])-2*住户[i][0];
}
临时总值[当前最累住户] = 0;
long l=1;
for (i = 0;i < 数量;i++) {
temp = 0;
for (j = 0;j < 数量;j++)
if (临时总值[temp] < 临时总值[j])
temp =j;
结果[l] = 结果[l - 1]+临时总值[temp];
临时总值[temp] = 0;
l++;
}
for (i = 0;i < 数量;i++) {
printf("%ld\n", 结果[i]);
}
return 0;
// system("pause");
} //为什么ac不了 我这里有的数据都通过了

#include<cstdio>
#include<queue>
using namespace std;
int s[100100],a[100100];
int Next[100100],Last,Now;
int n,t,sum;
priority_queue<int>Q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    Next[n+1]=n+1;
    s[n+1]=a[n+1]=0;
    for(int i=n;i>=1;i--)
    {
        t=Next[i+1];
        if(a[i]+s[i]*2>a[t]+s[t]*2)
            Next[i]=i;
        else Next[i]=t;
    }
    sum=0;
    Last=Now=0;
    for(int k=1;k<=n;k++)
    {
        Last=Now;
        t=Next[Last+1];
        if(Q.empty()||Q.top()+s[Last]*2<a[t]+s[t]*2)
        {
            sum+=a[t];
            printf("%d\n",sum+s[t]*2);
            Now=t;
        }
        else
        {
            sum+=Q.top();
            Q.pop();
            printf("%d\n",sum+s[Last]*2);
        }
        for(int i=Last+1;i<Now;i++)
            Q.push(a[i]);
    }
    return 0;
}

看见楼下是每次都暴力找的最大值，如果第一次最大值在1，第二次在2，第三次在3…这种情况下楼下的做法就退化到N^2了……可能是数据比较弱了吧（不过官方数据更弱）
所以我的思路和楼下差不多，不过用了线段树求最大值，严格的N log N。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int t[262145],tag[262145],S,n,pos;
int s[100010],a[100010];
priority_queue<int>Q;
void build() {
for (S=1;S<=n+1;S<<=1);
for (int i=1;i<=n;i++) {
t[S+i]=s[i]+a[i];
tag[S+i]=i;
}
for (int i=S-1;i>0;i--) {
if (t[i<<1]>=t[(i<<1)+1]) {
tag[i]=tag[i<<1];
t[i]=t[i<<1];
}
else {
tag[i]=tag[(i<<1)+1];
t[i]=t[(i<<1)+1];
}
}
return;
}
int query(int l) {
int ans=-1,r=S+n+1;
for (l+=S;l^r^1;l>>=1,r>>=1) {
if ((l&1)^1 && ans<t[l^1]) {
ans=t[l^1];
pos=tag[l^1];
}
if (r&1 && ans<t[r^1]) {
ans=t[r^1];
pos=tag[r^1];
}
}
return ans;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",s+i);
s[i]<<=1;
}
for (int i=1;i<=n;i++) {
scanf("%d",a+i);
}
build();
int now=0,total=0;
for (int num=1,ans,re;num<=n;num++) {
ans=-1;
if (!Q.empty())
ans=Q.top();
re=query(now)-s[now];
if (re>ans) {
total+=re;
for (int i=now+1;i<pos;i++) {
Q.push(a[i]);
}
now=pos;
}
else {
total+=Q.top();
Q.pop();
}
printf("%d\n",total);
}
return 0;
}

#include<cstdio>
#include<queue>
using namespace std;
int s[100100],a[100100];
int Last,Next,n,Sum,Best;
priority_queue<int>Q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    Sum=0;Next=0;
    for(int k=1;k<=n;k++)
    {
        Last=Next;
        if(!Q.empty())
            Best=Q.top()+s[Last]*2;
        else Best=0;
        for(int i=Last+1;i<=n;i++)
            if(a[i]+s[i]*2>Best)
            {
                Best=a[i]+s[i]*2;
                Next=i;
            }
        printf("%d\n",Sum+Best);
        if(Next==Last)
        {
            Sum+=Q.top();
            Q.pop();
        }
        else
        {
            for(int i=Last+1;i<Next;i++)Q.push(a[i]);
            Sum+=a[Next];
        }
    }
    return 0;
}

运用了两个堆 分别维护距离最远的推销点之前和之后的最大疲劳值推销点
```
#include<cstdio>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct nod{
int v,d;
bool operator <(const nod &a)const{
return v<a.v;
}
};
const int mn=100000+50;
priority_queue<nod> ri;
priority_queue<int> le;
int n,a[mn],s[mn],ans,md,t1,t2;
nod t;
int main(){
scanf("%d",&n);
fo(i,1,n)
scanf("%d",&s[i]);
fo(i,1,n)
scanf("%d",&a[i]);
fo(i,1,n){
ri.push((nod){a[i]+(s[i]<<1),i});
}
ri.push((nod){0,n+1});
le.push(0);
int i=0;
while (i<n){
t=ri.top();//
if (t.d<=md){
ri.pop();
continue;
}
t1=t.v-(s[md]<<1);

t2=le.top();//

if (t1>t2){
ri.pop();
ans+=t1;
fo(j,md+1,t.d-1)
le.push(a[j]);
md=t.d;
}
else{
le.pop();
ans+=t2;
}
printf("%d\n",ans);
i++;
}
return 0;
}
```

写了一个多小时AC。说一下思路。在下面的讨论中，假定入口在最左边。
观察样例，可以发现第 X-1 步选择的地点总是被包含在第 X 步选择的地点中。因此这题很可能具有贪心的可行性。仔细论证一下，可以证出这个结论是正确的。（可以运用反证法，类似 dijkstra算法 的证明方法）。
明白这一点后，算法的步骤即为：令集合 T 一开始为全体地点，sum=0。每一步从 T 中选取点 i，该点利益 E[i] 是各点中最大的，令 sum += E[i]，输出 sum，并将 i 点从 T 中删除。这里的利益指的是走到那个点**能增加的**的疲惫值。
那么利益\(E_i\)如何计算呢？很显然，一开始时\(E_i\)由下式给出
\(E_i = A_i + 2*S_i\)

然而当选取了一个点后，E[i]需要进行相应的更改。以下的讨论中，
假设之前被选中的 S 最大的点（即最靠右的点）为 prev，当前被选中的点为 this 。
1) 为了让 this 不再被选中，令
\(E_{this} = -\infty\)

2) 对于 prev 和 this 之间（不含端点）的所有点 i，若 \(S_{this} > S_{prev}\)：
\(E_i = E_i - 2*(S_i - S_{prev})\)

否则 E[i] 不变。意思是：若 this 比起 prev 还往前走了一段距离，那么显然在后续过程中这些点所能获得的利益将减少两倍的 i 与 prev 间的距离。若没有往前走，那么该点利益维持不变。

3) 对于 this 右边的所有点 i，若 \(S_{this} > S_{prev}\)：
\(E_i = E_i - 2 * (S_{this}-S_{prev})\)

否则 E[i] 不变。解释同情况 2。不明白的可以画图验证。

接下来需要考虑的问题是如何快速更新利益的值，并快速地找出其中的最大值。如果是纯暴力，每次需要 O(n) 来查询最大值与更新，总计是 O(n^2)，60分左右；如果用堆，每次查询需要 O(log n)，但更新需要 O(n log n)。还不如暴力。
因为涉及区间修改和查询，想到用线段树，维护区间最值，并需要支持区间更新。平摊下来查询与更新都是 O(log n)。之所以说是平摊，是因为第二种情况中，无法进行整段区间的更新，而只能单点更新（因为每个点减去的值不同），具体的时间复杂度是不定的。但是由于第二种情况对于每个点来说至多出现一次，单点更新的总次数是 O(n)，故平摊下来还是 O(log n)。

.毕竟超时..再让我改改...大家不要抄.......
#include<stdio.h>
int dis[100005]={0};
int a[100005]={0};
int p[100005]={0};
int heap[100005]={0};
int jinkela[100005]={0};
int n,len;
void put(int pi)
{
while(pi!=1&&heap[pi]>=heap[pi/2])
{
swap(pi,pi/2);
pi=pi/2;
}
return ;
}
void swap(int x,int y)
{
int ex;
ex=heap[x];
heap[x]=heap[y];
heap[y]=ex;
ex=jinkela[x];
jinkela[x]=jinkela[y];
jinkela[y]=ex;
return;
}
void maxheap(int pi)
{
int largest1;
largest1=max(pi,pi*2,pi*2+1);
if(largest1==pi) return;
else
{
swap(pi,largest1);
maxheap(largest1);
}
}
int max(int a,int b,int c)
{
int ans1;
if(c>len&&b>len) return a;
if(c>len)
{
if(heap[a]>heap[b]) return a;
if(heap[b]>heap[a]) return b;
}
if(b>len)
{
if(heap[a]>heap[c]) return a;
if(heap[c]>heap[a]) return c;
}
if(heap[a]>heap[b]) ans1=a;
else ans1=b;
if(heap[c]>heap[c]) return c;
if(heap[c]<heap[ans1]) return ans1;
}
int main()
{
int most,largest,i,tail,j,point,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&dis[i]);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
jinkela[i]=i;
}
for(i=1;i<=n;i++)
{
p[i]=2*dis[i]+a[i];
if(p[i]>ans)
{
ans=p[i];point=i;
}
}

printf("%d\n",ans);
p[point]=0;
largest=dis[point];//记录最远

most=a[point];
len=n-1;
for(j=1;j<n;j++)
{
tail=1;
for(i=1;i<=n;i++)
{
if(p[i]!=0)
{
if(dis[i]<=largest)
{
p[i]=ans+a[i];
}
if(dis[i]>largest)
{
p[i]=2*dis[i]+a[i]+ans-2*largest;
}
heap[tail]=p[i];
jinkela[tail]=i;
put(tail);
tail++;
}
}
printf("%d\n",heap[1]);
if(dis[jinkela[1]]>=largest)
{
largest=dis[jinkela[1]];
most=a[jinkela[1]];
}
ans=heap[1];
point=jinkela[1];
p[jinkela[1]]=0;
len--;
}
return 0;
}

题目的n范围不大对啊……实际上n绝对不止100000，开了100005我RE了……但是多加一个0 变成1000005就AC了！
代码写得有点难看……手写了优先级队列（主要是不会调用）。还是发出来吧……这个代码……

#define _CRT_SECURE_NO_DEPRECATE
#include<cstdio>
#include<iostream>
using namespace std;

long n, ld, lc, dis = 0, ans = 0;
long d[1000005] = { 0 }, a[1000005] = { 0 }, k[1000005] = { 0 }, treed[1000005] = { 0 }, treec[1000005] = { 0 };
bool used[1000005] = { false };

void correctc(long o) //c堆的从上向下的更正
{
long t, m;
long bigger;
if (o > lc) return;
if (a[treec[o * 2]] > a[treec[o * 2 + 1]])
{
m = 0;
bigger = a[treec[o * 2]];
}
else
{
m = 1;
bigger = a[treec[o * 2 + 1]];
}
if (a[treec[o]] < bigger)
{
t = treec[o];
treec[o] = treec[o * 2 + m];
treec[o * 2 + m] = t;
correctc(o * 2 + m);
}
}

void correctd(long o) //d堆的从上向下的更正
{
long t,m;
long bigger;
if (o > ld) return;
if (k[treed[o * 2]] > k[treed[o * 2 + 1]])
{
m = 0;
bigger = k[treed[o * 2]];
}
else
{
m = 1;
bigger = k[treed[o * 2 + 1]];
}
if (k[treed[o]] < bigger)
{
t = treed[o];
treed[o] = treed[o * 2 + m];
treed[o * 2 + m] = t;
correctd(o * 2 + m);
}
}

int main()
{
cin >> n;

ld = lc = n;
for (long i = 1; i <= n; i++)
scanf("%ld", &d[i]);
for (long i = 1; i <= n;i++)
{
scanf("%ld", &a[i]);
k[i] = d[i]*2 + a[i];
treed[i] = i;
treec[i] = i; //建立两个大根堆，d表示加权的（加距离的），c是没有加距离的。
}
for (long i = n / 2; i >= 1; i--)
{
correctc(i);
correctd(i); //对大根堆进行第一次调整。
}
used[0] = 0;
for (long i = 1; i <= n; i++)
{
while ((d[treed[1]] <= dis)&&(ld>0)) //不一定要使用，凡是小于等于dis就没有竞争力了，直接剔除。
{
treed[1] = treed[ld];
treed[ld] = 0;
ld--;

correctd(1);
}
while (used[treec[1]]) //用过的节点自然就被剔除了哦。
{
treec[1] = treec[lc];
treec[lc] = 0;
lc--;
correctc(1);
}
if (a[treec[1]] >= k[treed[1]] - dis * 2) //最大距离不变，从普通树里面弹出树根，纠正树，使用标记
{
ans += a[treec[1]];
used[treec[1]] = true;
treec[1] = treec[lc];
treec[lc] = 0;
lc--;
correctc(1);
}
else
{
ans += k[treed[1]] - dis*2; //此时改变最大距离是最优解，改变dis。使用标记
used[treed[1]] = true;
dis = d[treed[1]];
treed[1] = treed[ld];
treed[ld] = 0;
ld--;
correctd(1);
}
printf("%ld\n", ans);
}
// system("pause"); 这一行是因为用visual studio写 所以不得不写这个来调试……忽略掉
return 0;
}

贪心
X=x时的最优解集合为U(x), last(U)为U中s最大的元素
1. v∈U(n)-U(x-1)且满足∀u∈U(n)-U(x-1)-{v}, s[v]+a[v]≥s[u]+a[u], U(x)=U(x-1)∪{v}

1. ans+=s[v]+a[v], 输出

2. 若v>last(U(x-1)), 则∀u∈U(n)-U(x):

   1. s[u]改为0 | u<v
   2. s[u]减去s[v]-s[last(U(x-1))] | u>v

3. ++x, 若x>n结束, 否则跳至1

//还是看代码吧

贪心的最优性证明(瞎写, 请喷):
假设U(x)不是最优解, 即∃u∈U(n)-U(x),∃v∈U(x)使U'(x)=U(x)∪{u}-{v}优于U(x)
设r=last(U(x)), 由假设, 有s[r]+a[r],s[v]+a[v]≥s[u]+a[u], v≤r
1. 选择顺序为r→v
s[u]+a[u]>s[v]+a[v], 矛盾

1. 选择顺序为v→r
   有s[v]+a[v]≥s[r]+a[r]

   1. u<v
      a[u]>a[v]≥s[r]+a[r]-s[v]≥s[r]+a[r]-s[u]
      a[u]+s[u]>a[r]+s[r], 矛盾

   2. v<u<r
      a[u]+s[u]>a[v]+s[v], 矛盾

   3. r<u
      a[u]>a[v]≥s[r]+a[r]-s[v]
      a[u]+s[u]>s[r]+a[r]+s[u]-s[v]≥s[r]+a[r], 矛盾

综上, U(x)为最优解
//这个是priority_queue+O(n)预处理suffix维护最值.场上写的是segment tree维护最值, 100+行
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)

using namespace std;
const int N=100010;
char ch;
int ret,n,s[N],a[N],suf[N],sp[N],fst=1,ans,mxs;
priority_queue<int> h;

inline int getint()
{
while (!isdigit(ch=getchar()));
for (ret=ch-48; isdigit(ch=getchar()); ret=(ret<<3)+(ret<<1)+ch-48);
return ret;
}

int main()
{
n=getint();
rep(i,1,n)
s[i]=getint()<<1;
rep(i,1,n)
a[i]=getint();
repd(i,n,1)
if (suf[i+1]>s[i]+a[i])
suf[i]=suf[i+1],sp[i]=sp[i+1];
else
suf[i]=s[i]+a[i],sp[i]=i;
rep(i,1,n)
if (h.empty() || h.top()<suf[fst]-mxs)
{
printf("%d\n",ans+=suf[fst]-mxs);
rep(i,fst,sp[fst]-1)
h.push(a[i]);
fst=sp[fst]+1,mxs=s[fst-1];
}
else
printf("%d\n",ans+=h.top()),h.pop();
return 0;
}

这题我不会写，真是日了狗了。
求大神发题解，教我写。
就这样机智的水了一贴。

ppap

foo.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
测试数据 #0: Accepted, time = 15 ms, mem = 2612 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2612 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2612 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2612 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2612 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2612 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 2612 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 2608 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 2612 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 2612 KiB, score = 10
Accepted, time = 435 ms, mem = 2612 KiB, score = 100