1 条题解
-
0
//按疲劳值a排序 //要么取最大疲劳值的i个用户 + 其中的最大距离 //要么取最大疲劳值的i-1个用户+(后面疲劳加距离综合最大的元素) #include<bits/stdc++.h> using namespace std; int n; int sum[100005];//疲劳前缀和 int mju[100005];//前i个中的最大距离 int mzh[100005];//后i个中疲劳+距离综合最大值 struct node{ int s,a; }f[100005]; bool cmp1(node x,node y) { return x.a>y.a; } int main(){ freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); cin>>n; for(int i=1;i<=n;i++)scanf("%d",&f[i].s); for(int i=1;i<=n;i++)scanf("%d",&f[i].a); sort(f+1,f+1+n,cmp1); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+f[i].a; for(int i=1;i<=n;i++) mju[i]=max(mju[i-1], f[i].s*2); for(int i=n;i>=1;i--) mzh[i]=max(mzh[i+1], f[i].s*2 + f[i].a); for(int i=1;i<=n;i++) { printf("%d\n",max(sum[i]+mju[i], sum[i-1]+mzh[i])); } return 0; }
信息
- ID
- 647
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 16
- 已通过
- 2
- 上传者