题解：P2672 [NOIP2015 普及组] 推销员

· · 题解

P2672 [NOIP2015 普及组] 推销员

原题传送门

更好的阅读体验

解题思路

先考虑暴力。观察样例可知，X=i 时的最优解肯定包含 X=i-1 时的最优解。所以我们就会有一个思路：每次枚举新加入的点，计算一下添加这个点对答案的贡献是多少，取贡献最大的点即可。时间复杂度 O(n^2)。

再考虑优化。如果当前最远走到的距离是 S，那么对于某个点：如果 s_i>S，选这一个点答案就会加上 2(s_i-S)+a_i；如果 s_i\leq S 答案就会加上 a_i。

那么我们就会有一个贪心的思路，如果从 s_i>S 的点里面选就一定会选 2\times s_i+a_i 最大的；而如果从 s_i\leq S 里面选就一定会选 a_i 最大的。

这时可以想到，用两个大根堆分别维护当前 s_i\leq S 的点的所有 a_i 以及 s_i>S 的所有 2\times s_i+a_i，每次选两边对答案贡献较大的一个即可。但有时候 S 会增大，这时候需要在取堆顶时判掉一些 s_i <S 的点。

该做法时间复杂度 O(n \log n)，符合要求。

参考代码

#include<iostream>
#include<queue>
#define pii pair<int,int>
#define fi first
#define se second 
#define mp make_pair
using namespace std;
const int N=100005;
priority_queue<int> q1;
priority_queue<pii> q2;
int n,ans,now,maxx,maxn;
pii a[N],t;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].fi;//s
    for(int i=1;i<=n;i++) cin>>a[i].se;//a
    for(int i=1;i<=n;i++) q2.push(mp(2*a[i].fi+a[i].se,i));
    q1.push(0);
    for(int i=1;i<=n;i++){
        now=maxn;
        maxx=q1.top();
        while(!q2.empty()){
            t=q2.top();
            if(a[t.se].fi>=a[maxn].fi||maxn==0) break;
            q2.pop();
        }
        if(t.fi-2*a[maxn].fi>maxx&&!q2.empty()){
            maxn=t.se;
            maxx=t.fi-2*a[now].fi;
            for(int j=now+1;j<maxn;j++) q1.push(a[j].se);
            q2.pop();
        }
        else q1.pop();
        ans+=maxx;
        cout<<ans<<'\n';
    }
    return 0;
}

AC 记录