推销员 题解

思路:这道题明显贪心可以做,但是路程远近不好处理,所以需要稍加判断,我们在原题的基础上直接去用推销产品的疲劳值去排序,然后再从前到后和从哪后到前的顺序去排序每次走的路程(本题的路程分为两种情况:

1. 先走$m$再走$n$，$m>n$、那么总路程为$m$;
2. 先走$m$再走$n$，$m<n$，那么总路程就为$n$）；在以上的基础上去处理答案即可;

AC代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ans[1010101];
int ls[1010101];
int wc[1010101];
int sum[10101111];
int q[1010101],h[1010101];
struct node{
	int wc,ans;
	 bool operator <(const node &a)const{
		return ans>a.ans;//以结构体中的ans（每一家推销的疲劳值）为比较对象
	}
}tmd[1010101];
int main(){
//	freopen("salesman.in","r",stdin);
//	freopen("salesman.out","w",stdout);//在比赛过程中记得加入freopen
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>tmd[i].wc;	
		
	}
	for(int i=1;i<=n;i++){
		int z;
		cin>>tmd[i].ans;
		
	}//输入，记录数据
sort(tmd+1,tmd+1+n);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+tmd[i].ans;//记录推销给每家的疲劳值
	}
	for(int i=1;i<=n;i++)q[i]=max(q[i-1],2*tmd[i].wc);//先从前往后，也就是思路中的1；
    for(int i=n;i>=1;i--)h[i]=max(h[i+1],2*tmd[i].wc+tmd[i].ans);//思路中的2；主语路程往返要*2
    for(int i=1;i<=n;i++) cout<<max(sum[i]+q[i],sum[i-1]+h[i])<<endl;//输出两种情况中较大的一个
	return 0;
}

欢迎加入团队