健身

声明：通过这道题的几份代码都是错的，能AC可能是因为测试数据设计不合理。以下是我的3份代码，欢迎大家一起讨论。

# coding:utf-8
import sys
import heapq
if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    distance_list = map(int, str(sys.stdin.readline().strip()).split())
    val_list = map(int, str(sys.stdin.readline().strip()).split())
    distance_val_list = []
    for i in range(n):
        distance_val_list.append((distance_list[i], val_list[i]))
    distance_val_list.sort(key=lambda x: x[0])

    # 可以证明选择k+1种锻炼方式可由选择k种锻炼方式扩展一个节点生成，维护两个堆，时间复杂度为O(nlogn)，得分100
    left_heap = []
    right_heap = []
    farthest_index = -1
    chosen_set = set()
    for i in range(n):
        heapq.heappush(
            right_heap, (-(2 * distance_val_list[i][0] + distance_val_list[i][1]), i))
        heapq.heappush(
            left_heap, (-distance_val_list[i][1], i))
    ans = 0
    while left_heap or right_heap:
        right_val = 0
        right_index = -1
        left_val = 0
        left_index = -1
        while right_heap and (right_heap[0][1] in chosen_set or right_heap[0][1] < farthest_index):
            heapq.heappop(right_heap)
        if right_heap:
            right_val, right_index = -right_heap[0][0], right_heap[0][1]
            if farthest_index >= 0:
                right_val -= 2 * distance_val_list[farthest_index][0]
        while left_heap and left_heap[0][1] in chosen_set:
            heapq.heappop(left_heap)
        if left_heap:
            left_val, left_index = -left_heap[0][0], left_heap[0][1]
        if not (left_heap or right_heap):
            break
        if left_val > right_val:
            heapq.heappop(left_heap)
            chosen_set.add(left_index)
            ans += left_val
        else:
            heapq.heappop(right_heap)
            chosen_set.add(right_index)
            farthest_index = right_index
            ans += right_val
        print ans

    # 可以证明选择k+1种锻炼方式可由选择k种锻炼方式扩展一个节点生成，线性查找，时间复杂度为O(n^2)，得分60
    farthest_index = -1
    count = 0
    chosen_set = set()
    ans = 0
    while count < n:
        max_val = 0
        index = -1
        for i in range(n):
            if i not in chosen_set:
                if i < farthest_index:
                    val = distance_val_list[i][1]
                elif i > farthest_index:
                    if farthest_index < 0:
                        val = 2 * \
                            distance_val_list[i][0] + distance_val_list[i][1]
                    else:
                        val = 2 * \
                            (distance_val_list[i][0] - distance_val_list[farthest_index]
                             [0]) + distance_val_list[i][1]
                else:
                    assert False
                if val > max_val:
                    max_val = val
                    index = i
        chosen_set.add(index)
        if index > farthest_index:
            farthest_index = index
        ans += max_val
        print ans
        count += 1

    # 没有用上边两种方法用到的结论，直接暴力dp（实际上可以用一维数组，懒得写了），时间复杂度为O(n^3)，得分40
    dp = [[] for i in range(n)]
    for j in range(n):
        dp[0].append(2 * distance_val_list[j][0] + distance_val_list[j][1])
    for i in range(1, n):
        for j in range(0, n):
            if i > j:
                dp[i].append(0)
            else:
                max_val = 0
                for k in range(0, j):
                    max_val = max(
                        max_val, dp[i - 1][k] + 2 * (distance_val_list[j][0] - distance_val_list[k][0]))
                dp[i].append(max_val + distance_val_list[j][1])
    for i in range(n):
        print max(dp[i])

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int id;
    int dis;
    int ex;
};
//重载运算符，按其和作为优先指标，注意'<'表示大顶堆
struct cmpSum{
    bool operator()(Node a,Node b){
        return 2 * a.dis + a.ex < 2 * b.dis + b.ex;
    }
};
//以其ex值作为优先指标
struct cmpEx{
    bool operator()(Node a, Node b){
        return a.ex < b.ex;
    }
};
int main(void){
    int N;
    cin >> N;
    vector<int> dis(N+1,0),ex(N+1,0);
    int temp;
    for (int i = 1; i <= N; i++){
        cin >> temp;
        dis[i] = temp;
    }
    for (int i = 1; i <= N; i++){
        cin >> temp;
        ex[i] = temp;
    }
    //两个优先队列
    priority_queue<Node,vector<Node>,cmpSum> queueSum;
    priority_queue<Node,vector<Node>,cmpEx> queueEx;
    //O(2nlogn)
    for(int i = 1; i <= N; i++){
        queueSum.push(Node{i,dis[i],ex[i]});
        queueEx.push(Node{i,dis[i],ex[i]});
    }
    int ans = 0, newMax = 0, preFar = 0;
    int newIndex = 0;
    int cur1, cur2;
    //记录用过的结点
    vector<int> visited(N + 1, 0);
    //可选择i种器材，O(N)
    for (int i = 1; i <= N; i++){
        //懒更新，某个器材用过了不会立刻弹出队列，仅在visited数组中记录
        //如果它在队首，才弹出
        while(!queueSum.empty() && visited[queueSum.top().id]){
            queueSum.pop();
        }
        while(!queueEx.empty() && visited[queueEx.top().id]){
            queueEx.pop();
        }
        //查看两个队列的队首，新加入的器材必定在其中一个队列的队首
        //新加入的器材有可能比之前最远的器材远，也可能近
        //其中一部分贡献是自的ex值
        //如果更远的话，那还有一部分贡献是比之前最远多出来的部分的两倍
        //找出贡献值最大的那个器材的下标
        cur1 = 2 * max(0,(queueSum.top().dis - preFar)) + queueSum.top().ex;
        cur2 = 2 * max(0,(queueEx.top().dis - preFar)) + queueEx.top().ex;
        if (max(cur1, cur2) > newMax){
            newMax = max(cur1,cur2);
            //选择后要记录id，用于之后的访问标记与更新最远距离
            if (cur1 >= cur2) newIndex = queueSum.top().id;
            else newIndex = queueEx.top().id;
        }
        //从i-1种器材到i种，就是原答案基础上加上新的贡献
        ans += newMax;
        //记录当前最远的器材
        preFar = max(preFar, dis[newIndex]);
        //加上访问标记
        visited[newIndex] = 1;
        newMax = 0;
        cout << ans << endl;
    }
}

N=int(input())
distance = list(map(int,input().split()))
exp = list(map(int,input().split()))
 
pure=sorted(enumerate(exp),key=lambda x:x[1],reverse=True) #只有自己锻炼效果的排序
#加上走路距离的效果排序
comp=sorted(enumerate([exp[i]+distance[i]*2 for i in range(N)]),key=lambda x:x[1],reverse=True)

currentMaxIndex=-1  #记录前i个锻炼效果最大值的最大下标
currentMaxExp=0  #记录前i个锻炼效果最大值的总和

for i in range(N):
    j=0
    if currentMaxIndex==N-1:
        #节省了下面while的很多次比较
        currentMaxExp+=pure[i][1]
        print(currentMaxExp+2*distance[currentMaxIndex])
        continue
        
    while comp[j][0]<=currentMaxIndex:
        j+=1
    tmp0=currentMaxExp+comp[j][1] #tmp0记录从前i-1个最大值的后面选取一个运动的效果最大值
    if currentMaxIndex>0:
        #tmp1记录从当前的最大下标之前选取一个运动的效果最大值
        tmp1=currentMaxExp+pure[i][1]+2*distance[currentMaxIndex]
    else:
        tmp1=0
    print(max(tmp0,tmp1))
    currentMaxExp+=pure[i][1]
    currentMaxIndex=max(currentMaxIndex,pure[i][0])