很水的一道黑

传送门

题目大意

给出 \(n\) 个元素，每个元素有两个权值 \(a_i\) 和 \(b_i\),从中选出若干元素,

令取出元素的 \(a_i\) 之和为 \(S_a\) ,其余元素的 \(b_i\) 之和为 \(S_b\) ,最大化 \(S_a*S_b\)

分析

可以知道 \(a_i\) , \(b_i\) 的值分别在 \([1,A]\) , \([1,B]\) 间均匀随机生成;

所以 \(a_i\) , \(b_i\) 之和相差并不大，贪心选更大的即可得出最优解;

可以按 \(\frac{a_i}{b_i}\) 排好序后在中点附近枚举断点,差不多枚举 \(100\) 个即可;

最后断点左边都选 \(b_i\) ,右边都选 \(a_i\)，得出的结果取 \(max\) ,记得开 \(int\underline{\;\;}128\);

优化

但是当 \(a_i\) , \(b_i\) 本身相差很小甚至相等时,按如上方法求解很容易举出反例

所以每个断点附近还要进行几次暴搜来保证正确性(实测搜 \(10\) 个即可)

代码

#include <bits/stdc++.h>
#define cys __int128
using namespace std;
const int maxn=3009;
int T,n;
long long A,B;
cys ans,l,r;
struct node{
	cys a,b;
}s[maxn];
inline cys read(){
	cys res=0;char c=getchar();
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+(c^48);
	return res;
}
void write(cys x){
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
bool cmp(node x,node y){return 1.0*x.a/x.b>1.0*y.a/y.b;}
cys dfs(int step,cys X,cys Y){
	if(step==r+1) return X*Y;
	return max(dfs(step+1,X+s[step].a,Y),dfs(step+1,X,Y+s[step].b));
}
int main(){
	scanf("%d%d%lld%lld",&T,&n,&A,&B);
	while(T--){
		for(int i=1;i<=n;i++) s[i].a=read(),s[i].b=read();
		sort(s+1,s+n+1,cmp);ans=0;
		for(int k=max(1,n/2-50);k<=min(n,n/2+50);k++){
			cys x=0,y=0;
			l=max(1,k-5),r=min(n,k+5);
			for(int i=1;i<l;i++) x+=s[i].a;
			for(int i=r+1;i<=n;i++) y+=s[i].b;
			ans=max(ans,dfs(l,x,y));
		}
		write(ans),puts("");
	}
	return 0;
}

那么多随机算法标签结果只有数据是随机的