嗯...

 

题目链接：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：

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

AC代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
            5  6 using namespace std; 7  8 const int maxn = 100005; 9 10 struct node{11     int w, id, ans;12     node() { }13     bool operator < (const node & p) const{14         return w + 2 * id < p.w + 2 * p.id;15     }//重载运算符 16 } e[maxn];17 18 19 priority_queue 
          
            a;//左边点 20 priority_queue 
           
             b;//右边点 21 22 int m, cnt, n, k, j;23 24 inline void fir(){25 m = b.top().ans;//第一个值为最大值 26 printf("%d\n", m);27 cnt = n - 1;//cnt用来记录当前i 28 k = b.top().id;//k转移到最大值的id 29 b.pop();30 for(j = 1; j <= n; j++){31 if(e[j].id >= k) break;//右边点 32 else a.push(e[j].w);//左边点 33 }//更新 34 }//第一次 35 36 inline void solve(){37 while(cnt--){38 if(b.top().ans - 2 * k >= a.top()){39 if(b.top().id <= k){ //更新，若原右边点现在在左边 40 b.pop();41 cnt++;42 continue;43 }//右边堆顶比左边堆顶大 44 m += b.top().ans - k * 2;//加最大值 45 k = b.top().id;//k转移 46 b.pop();47 while(j++ <= n){48 if(e[j].id >= k) break;49 else{50 a.push(e[j].w);51 b.pop();52 }//右边转移到左边 53 }54 }55 else{56 m += a.top();57 a.pop();58 }//左边堆顶大 59 printf("%d\n", m);60 }61 }62 63 64 int main(){65 scanf("%d", &n);66 for(int i = 1; i <= n; i++) scanf("%d", &e[i].id);67 for(int i = 1; i <= n; i++){68 scanf("%d", &e[i].w);69 e[i].ans = e[i].w + 2 * e[i].id;70 b.push(e[i]);71 }72 fir();73 solve();74 return 0;75 }