洛谷P2672 推销员

106 阅读 0 评论 70 点赞

我是靠谱客的博主淡淡鲜花，这篇文章主要介绍洛谷P2672 推销员，现在分享给大家，希望可以做个参考。

题目连接
https://www.luogu.org/problem/show?pid=2672
贪心+优先队列
解题思路：
可以将题目视为边走边推销，对于每一次决策都有两种选择：
1.继续向前走，此时的疲劳值是向前走的疲劳值加上推销的疲劳值；
2.不向前走，往回去，此时已经走完路了，所以不需要加上路上的疲劳值；
因为每次决策都取最大的疲劳值，所以最后的结果就是最大的，可以用优先队列来储存每一次的最大值；
用now标记最远能够到达的距离，maxx记录每一次决策花费的最大疲劳值，用mx更新now；
因为有往返距离，每次都要算两倍的距离，开始能向前走就向前走，并且顺路推销，如果不能向前走了，就回来推销。用ans累加上q.top（）就可以了。
优先队列中一定要先压入起点0，不然会出错

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  #include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int>q;
struct node{
    int d,v;
}a[100005];
int ans,n,maxx,mx,now;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].d;
    for (int i=1;i<=n;i++) cin>>a[i].v;
    q.push(0);
    for (int i=1;i<=n;i++){
        maxx=q.top();mx=now;
        for (int j=now+1;j<=n;j++)
        if ((a[j].d-a[now].d)*2+a[j].v>=maxx)
        maxx=(a[j].d-a[now].d)*2+a[j].v,mx=j;
        if (mx!=now)
        q.push(maxx);
        for (int j=now+1;j<mx;j++)
        q.push(a[j].v);
        now=mx;
        ans+=q.top();
        q.pop();    
        cout<<ans<<endl;
    }

    return 0;
}