为何二分答案都不对,这在某种意义上不就是暴力吗,此代码虽过样例但 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;
}