推(chuan)销员
分析
这里主要阐述一下我的分析思路。
看起来挺直观的。
最初的想法，我们枚举每一个最远点mxp的位置，然后对之前的a进行排序。
那么以mxp为最远点，选x个的最大疲劳值为：
这样的复杂度为，考试时就这样拿了个60pt。
但是，我们要尝试发现这道题的特性，来进行时间上的优化。
根据极大化思想，我们要尽可能排除不影响答案的。
当一定时，设，没有优，这等价于：
记
当增大的时候，例如变大到，发现的值一定是递增的，因为一定是多一个数，也一样，而能选择到的也能选择得到。
所以我们得到了决策单调性：对于，，没有优，那么随着的增大，仍然没有优，所以对于的询问的决策点会非严格单调递增。
接下来，很容易想到用单调队列什么的进行维护。
但怎么尝试都觉得不行……
这时候就一定要跳出来啦。
根据决策单调性这个重要的特点，考虑换一种思考的角度。
假如当前这个询问我们决策点为，答案为，现在要求这个询问的决策点和答案。
我们有两种方法：
①在之前选择一个没有选择过的点，
②在之后选择一个决策点，
用两个堆实现即可。
有点意思。
代码
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define x first
#define y second
#define mp make_pair
typedef pair<int,int> PII;
const int N=131072;
int n;
int s[N],a[N];
int cur,vis[N];
priority_queue<PII> qs,qb;
int res;
inline int rd(void)
{
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int main(void)
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=rd();
rep(i,1,n) s[i]=rd();
rep(i,1,n) a[i]=rd();
rep(i,1,n)
qb.push(mp(2*s[i]+a[i],i));
PII t1,t2; int e1,e2,cs;
rep(i,1,n)
{
while (!qs.empty())
{
t1=qs.top();
if (vis[t1.y])
qs.pop();
else break;
}
while (!qb.empty())
{
t2=qb.top();
if (t2.y<cur||vis[t2.y])
qb.pop();
else break;
}
e1=(!qs.empty());
e2=(!qb.empty());
if (!e1&&e2)
cs=2;
else if (e1&&!e2)
cs=1;
else if (e1&&e2)
{
t1=qs.top(),t2=qb.top();
if (t2.x-2*s[cur]>=t1.x)
cs=2;
else cs=1;
}
if (cs==1)
{
t1=qs.top(); qs.pop();
vis[t1.y]=1;
res+=t1.x;
}
else if (cs==2)
{
t2=qb.top(); qb.pop();
vis[t2.y]=1;
rep(j,cur+1,t2.y)
if (!vis[j])
qs.push(mp(a[j],j));
res+=(t2.x-2*s[cur]);
cur=t2.y;
}
printf("%d\n",res);
}
return 0;
}