题解 P2672 【推销员】

我不知道你们的方法为什么这么复杂 首先我们找到直接推销疲劳值最大的那个，就可以得到X=1的解，然后将now定为这个最大的住户的位置 接下来，我们将两边的居民分开考虑 对于左边的居民，不用走过多的路了，直接顺带推销掉，那么额外的疲劳值就只有推销所花的疲劳值。 对于右边的居民，我们求出s[j]×2-s[now]×2+a[j]最大的j 下面，我们取左边居民中净疲劳值（只包括推销的）最大的设为lmax，取右边最大的rmax=s[j]×2-s[now]×2+a[j]，然后比较两值，如果左边的大，那么推销那一家，ans+=lmax，否则将now定为最大的j，然后ans+=rmax，再将 oldnow+1至newnow-1的全部住户进堆 那么左边的最大值可以用堆，复杂度降至nlogn 看程序吧 ```cpp #define maxn 100000+500 #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib> using namespace std; int s[maxn],a[maxn]; struct max_heap //大根堆模板 { int size; int d[maxn]; void push(int x) //插入元素 { d[++size]=x; int flag=1,p=size; while (flag && (p>1)) { if (d[p/2]<d[p]) swap(d[p/2],d[p]); else flag=0; p/=2; } } void pop() //弹出堆顶 { swap(d[1],d[size]); size--; int p=1,t,flag=1; while (flag && (p*2<=size)) { if (d[p*2]>d[p]) t=p*2; else t=p; if (p*2<size) if ((d[p*2+1]>d[p]) && (d[p*2+1]>d[p*2])) t=p*2+1; if (t!=p) { swap(d[p],d[t]); p=t; } else flag=0; } } int top() //取堆顶 { return d[1]; } }h; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&s[i]); for (int i=1;i<=n;++i) scanf("%d",&a[i]); int ma=0,now; for (int i=1;i<=n;++i) if (a[i]+s[i]*2>ma) //计算X=1时的ans { ma=a[i]+s[i]*2; now=i; } int ans=ma; printf("%d\n",ans); for (int i=1;i<now;++i) h.push(a[i]); //将左边的值压入大根堆，为之后取最大值做准备 for (int i=1;i<n;++i) { int lmax=h.top(); //取左边的最大值 int rmax=0,rn=0; for (int j=now+1;j<=n;++j) if (a[j]+s[j]*2-s[now]*2>rmax) //枚举右边的，去一个最大的 { rmax=a[j]+s[j]*2-s[now]*2; rn=j; } if (lmax>rmax) //如果左边大 { ans+=lmax; h.pop(); //弹出堆顶 } else { ans+=rmax; for (int j=now+1;j<rn;++j) h.push(a[j]); //依次进堆，因为这些都在now的左边 now=rn; } printf("%d\n",ans); } return 0; } ```