#include <iostream> #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int N=100005; struct line { int v,s; bool operator < (line a) const { return v<a.v; } }t[N],s; priority_queue<line> q; int sum,n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&t[i].s); for(int i=1;i<=n;i++) scanf("%d",&t[i].v); s.s=s.v=0; q.push(s); int now=0,maxx=0; for(int i=1;i<=n;i++) { int next=now; s=q.top(); maxx=s.v; for(int j=now+1;j<=n;j++) { if(t[j].v+(t[j].s-t[now].s)*2>maxx) { maxx=t[j].v+(t[j].s-t[now].s)*2; next=j; } } t[next].v+=(t[next].s-t[now].s)*2; if(next!=now) q.push(t[next]); for(int j=now+1;j<next;j++) q.push(t[j]); s=q.top(); sum+=s.v; printf("%d\n",sum); q.pop(); now=next; } return 0; }

思路:这道题明显贪心可以做,但是路程远近不好处理,所以需要稍加判断,我们在原题的基础上直接去用推销产品的疲劳值去排序,然后再从前到后和从哪后到前的顺序去排序每次走的路程(本题的路程分为两种情况: 1. 先走mmm再走nnn，m>nm>nm>n、那么总路程为mmm; 2. 先走mmm再走nnn，m<nm<nm<n，那么总路程就为nnn）；在以上的基础上去处理答案即可; AC代码 欢迎加入团队

考虑我们如何将答案最大化：对于每个x，一定是选择(一个最大的s)+(x-1个最大的a)或者x个最大的a，可以使答案最优 那么具体怎么实现呢 我们先把数组按照a排序 我们用sum[i]表示a数组的前i项的和，q[i]表示s数组的前i项的最大值，h[i]表示a[i]2+s[i]后i项的最大值，对于每个x，他的答案就是max(sum[x]+2q[x],sum[x-1]+h[x])

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; struct po{ int s,a; }f[100010]; const int N=100010; int n; int p[N],q[N],sum[N]; bool cmp(po x,po y){ return x.a>y.a; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>f[i].s; for(int i=1;i<=n;i++) cin>>f[i].a; sort(f+1,f+1+n,cmp); for(int i = 1;i <= n;i++) sum[i]=sum[i-1] + f[i].a; for(int i = 1;i <= n;i++) p[i]=max(p[i-1],2f[i].s); for(int i = n;i >= 1;i--) q[i]=max(q[i+1],2f[i].s+f[i].a); for(int i = 1;i <= n;i++) cout<<max(sum[i]+p[i],sum[i-1]+q[i])<<endl; return 0; }