为何二分答案都不对,这不是简单暴力吗
查看原帖
为何二分答案都不对,这不是简单暴力吗
1057821
sad_lin楼主2024/11/27 13:02

为何二分答案都不对,这在某种意义上不就是暴力吗,此代码虽过样例但 WA on 2。

wrong answer 5483rd numbers differ - expected: '13', found: '12'

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
#define pb push_back
#define pir pair<int,int>
#define f1(x) for(int i=1;i<=x;i++)
#define f0(x) for(int i=0;i<=x;i++)
#define fr1(x) for(int i=x;i>=1;i--)
#define fr0(x) for(int i=x;i>=0;i--) 
const int N=2e5+10,M=25005;
const int mod=1e9+7;
using namespace std;

int n,m;
struct ss{
	int x,y;
}a[N];

bool cmp(ss g,ss h){
	return g.x<h.x;
}

int ans=0;

void check(int midd,int ax,int ay,int bx,int by,int las){
	int l=0,r=by,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(mid<=las/bx){
			ans=max(ans,ax*midd+mid*bx);
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
}

void find(int i1,int i2){
	int ax=a[i1].x,ay=a[i1].y;
	int bx=a[i2].x,by=a[i2].y;
	
	int l=0,r=ay,mid;
	
	while(l<=r){
		mid=(l+r)>>1;
		if(mid<=m/ax){
			check(mid,ax,ay,bx,by,m-mid*ax);
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	
	l=0,r=by;
	
	while(l<=r){
		mid=(l+r)>>1;
		if(mid<=m/bx){
			check(mid,bx,by,ax,ay,m-mid*bx);
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
}

void find2(int i1){
	int ax=a[i1].x,ay=a[i1].y;
	
	int l=0,r=ay,mid;
	
	while(l<=r){
		mid=(l+r)>>1;
		if(mid<=m/ax){
			ans=max(ans,mid*ax);
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
}

void solve(){
	ans=0;
	cin>>n>>m;
	
	f1(n){
		cin>>a[i].x;
	}
	f1(n){
		cin>>a[i].y;
	}
	
	sort(a+1,a+n+1,cmp);
	
	f1(n){
		find2(i);
		if(a[i].x==a[i+1].x-1){
			find(i,i+1);	
		}
	}
	cout<<ans<<"\n";
}


signed main(){
//	freopen("xp1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    int t;
    cin>>t;
    while(t--){
    	solve();
    	
	}
	return 0;
}
2024/11/27 13:02
加载中...