洛谷 P2672 推销员

题目传送门

解题思路:

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

本题要求最大的疲劳值,所以我们需要排序,第一个想到堆,反正我是先想到堆.

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

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

2.比当前k点距离原点更远,这些点的疲劳值其实就是推销疲劳值+两倍路径疲劳值-两倍k的路径疲劳值

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

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

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

代码处理的一些细节:

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

2.每当我更新一个k,我再将k左边所有的点推进左边堆.不这么做也可,只是这样代码好写

3.那么我们更新k后怎么判断右边堆那些在当前k的左边呢?因为k是动态的,所以原来在右边的可能到右边我们只要判断当前元素和k谁到原点近即可,所以我们要不单要记录疲劳值,还要记录路径值,所以我们要定义结构体来构造堆.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 struct node {
 9     int v, distance,ans;//推销值,距离值,最终值 
10     node() { }
11     bool operator < (const node & p) const {
12         return v + 2 * distance < p.v + 2 * p.distance;//按照疲劳值由大到小排序 
13     }
14 }e[100001];
15 
16 struct kkk {
17     int _v,_distance;
18 }_e[100001];
19 
20 priority_queue <node> b;//右边堆 
21 priority_queue <int> a;//左边堆 
22 int n,A,vv[100001],k,bj,m,n1;
23 
24 bool cmp(kkk aa,kkk bb) {
25     return aa._distance < bb._distance;
26 }
27 
28 void solve() {//解题过程 
29     while(n1--) {
30         if(b.top().ans - 2 * k >= a.top()) {//我忍不住要吐槽,将ans改成v,能得一半分,另一半TLE,这数据太弱了,害得我以为自己代码时间复杂度太高 
31             if(b.top().distance <= k) {
32                 b.pop();
33                 n1++;
34                 continue;
35             }
36             m += b.top().ans - 2 * k;
37             k = b.top().distance;
38             b.pop();
39             for(;bj <= n; bj++) 
40                 if(_e[bj]._distance >= k)
41                     break;
42                 else
43                     a.push(_e[bj]._v);
44         }
45         else {
46             m += a.top();
47             a.pop();
48         }    
49         printf("%d
",m);
50     }
51 }
52 
53 void firstime() {//第一次处理,之后便与解题思路一致 
54     m = b.top().ans;
55     cout << m << endl;
56     n1 = n;
57     n1--;
58     k = b.top().distance;
59     b.pop();
60     for(bj = 1;bj <= n; bj++)
61         if(_e[bj]._distance >= k)
62             break;
63         else
64             a.push(_e[bj]._v);
65 } 
66 
67 int main()
68 {
69     scanf("%d",&n);
70     for(int i = 1;i <= n; i++) {
71         scanf("%d",&e[i].distance);
72         _e[i]._distance = e[i].distance;    
73     }
74     for(int i = 1;i <= n; i++) {
75         scanf("%d",&vv[i]);
76         _e[i]._v = e[i].v = vv[i];
77         e[i].ans = e[i].v + 2 * e[i].distance;
78         b.push(e[i]);
79     }
80     sort(_e+1,_e+1+n,cmp);//按照距离原点远近排序 
81     firstime();
82     solve();
83     return 0;
84 }

//NOIP普及 2015 T4