难道这题还有O(logn)的方法?
查看原帖
难道这题还有O(logn)的方法?
682044
czk111楼主2022/8/17 15:45

这时我的代码,在洛谷上AC的,但在我老师的网站上就不行。

#include <bits/stdc++.h>
using namespace std;
int sum[100000],b[100000],f[100000],n;
struct node{
	int x;
	int y;
}a[100000];
bool cmp(node a,node b){
	return a.y>b.y;
}
int main){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i].x;
	for(int i=0;i<n;i++) cin>>a[i].y;
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++) sum[i]=sum[i-1]+a[i].y;
	for(int i=0;i<n;i++) f[i]=max(f[i-1],2*a[i].x);
	for(int i=n-1;i>=0;i--) b[i]=max(b[i+1],2*a[i].x+a[i].y);
	for(int i=0;i<n;i++) cout<<max(sum[i]+f[i],sum[i-1]+b[i])<<endl;
}

唉,老师的数据太坑了,正解都过不去

2022/8/17 15:45
加载中...