洛谷 P2672 推销员

嗯...

 

题目链接：https://www.luogu.org/problem/P2672

 

这个题是一个贪心的思想...

我们会发现本题有一个特性，就是如果我们走到一个更远的地方，那么近的地方距离原点的距离我们可以忽略.

最后疲劳值是由两部分组成的：路径疲劳值和推销疲劳值.又因为第一行提到的，所以我们可以选一个点k(后面解释)，将每个状态下分为两种点:

1.在当前k点的左面，这些点的疲劳值其实只有推销疲劳值，因为我们已经走得更远了，所以顺道处理这些就行，不需要走多余的路

2.比当前k点的右面，这些点的疲劳值其实就是推销疲劳值+两倍路径疲劳值-两倍k的路径疲劳值

而其实最大疲劳值就是这两种点各自的最大值的最大值，所以我们可以用两个大根堆来存，取两个堆顶的较大值即可.

返回来，k是什么呢？k就是我们当前已经选过的点里最靠右的

为什么呢？因为对我们来说只要某个点走了，则这个点左边所有点我们都可以顺路经过，并不需要多余路径疲劳值,所以我们只要记录最右即可.

代码处理的一些细节：

1.一开始右边的堆将所有点放进去，左边堆为空，选一个最大点为第一个k

2.每当更新一个k，再将k左边所有的点推进左边堆

3.那么我们更新k后怎么判断右边堆那些在当前k的左边呢?因为k是动态的，所以原来在右边的可能到右边我们只要判断当前元素和k谁到原点近即可，

所以我们要不单要记录疲劳值，还要记录路径值，所以我们要定义结构体来构造堆

//思路来自PD大佬lpy：https://www.cnblogs.com/lipeiyi520/p/11037364.html

外加自己的优化（优化掉了很多东西

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue> 

using namespace std;

const int maxn = 100005;

struct node{
    int w, id, ans;
    node() { }
    bool operator < (const node & p) const{
        return w + 2 * id < p.w + 2 * p.id;
    }//重载运算符 
} e[maxn];


priority_queue <int> a;//左边点 
priority_queue <node> b;//右边点 

int m, cnt, n, k, j;

inline void fir(){
    m = b.top().ans;//第一个值为最大值 
    printf("%d
", m);
    cnt = n - 1;//cnt用来记录当前i 
    k = b.top().id;//k转移到最大值的id 
    b.pop();
    for(j = 1; j <= n; j++){
        if(e[j].id >= k) break;//右边点 
        else a.push(e[j].w);//左边点 
    }//更新 
}//第一次 

inline void solve(){
    while(cnt--){
        if(b.top().ans - 2 * k >= a.top()){
            if(b.top().id <= k){//更新，若原右边点现在在左边 
                b.pop();
                cnt++;
                continue;
            }//右边堆顶比左边堆顶大 
            m += b.top().ans - k * 2;//加最大值 
            k = b.top().id;//k转移 
            b.pop();
            while(j++ <= n){
                if(e[j].id >= k) break;
                else{
                    a.push(e[j].w);
                    b.pop();
                }//右边转移到左边 
            }
        }
        else{
            m += a.top();
            a.pop();
        }//左边堆顶大 
        printf("%d
", m);
    }
}
                

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &e[i].id);
    for(int i = 1; i <= n; i++){
        scanf("%d", &e[i].w);
        e[i].ans = e[i].w + 2 * e[i].id;
        b.push(e[i]);
    }
    fir();
    solve();
    return 0;
}