top1编程
← 返回题目
题解

【提高】推销员

1 条题解

  • 0
    @ 2026-7-29 0:15:48
    #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;
    }
    
    • 1