着急,必定互关
by SiuuuCR7 @ 2024-04-21 20:41:31
@[SiuuuCR7](/user/1339828)
二分答案
by _qingshu_ @ 2024-04-21 20:54:32
哦,抱歉,不是二分答案,没有看全。
by _qingshu_ @ 2024-04-21 20:55:37
@[_qingshu_](/user/602803) 只有10分
by SiuuuCR7 @ 2024-04-21 20:55:49
@[SiuuuCR7](/user/1339828)
可以对于按编号排序后两两相邻的宝可梦算出使得排序合法的区间,然后就会有 $n-1$ 个区间,求交就好了。
by _qingshu_ @ 2024-04-21 20:57:31
@[_qingshu_](/user/602803) 这题可以用二分做啊
by SiuuuCR7 @ 2024-04-21 21:00:12
@[SiuuuCR7](/user/1339828)
可以吗?好像不具备单调性
by _qingshu_ @ 2024-04-21 21:07:36
大概是这样吧,不确定是不是对的。
```cpp
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
pair<pair<int,int>,int>a[5200010];
int n,lef=0,rig=INT_MAX;
inline bool cmp(pair<pair<int,int>,int>x,pair<pair<int,int>,int>y){
return x.S>y.S;
}
inline void solve(){
lef=0,rig=INT_MAX;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].F.F;
for(int i=1;i<=n;i++)cin>>a[i].F.S;
for(int i=1;i<=n;i++)cin>>a[i].S;
stable_sort(a+1,a+n+1,cmp);
for(int i=1;i<n;i++){
if(a[i].F.S==a[i+1].F.S){
if(a[i].F.F>=a[i+1].F.F){
cout<<-1<<"\n";return;
}
}
else if(a[i+1].F.S>a[i].F.S){
int now=max(0,a[i].F.F-a[i+1].F.F);
now=now/(a[i+1].F.S-a[i].F.S)+1;
if(rig<now){
cout<<-1<<"\n";return;
}
lef=max(lef,now);
}
else{
if(a[i+1].F.F<=a[i].F.F){
cout<<-1<<"\n";return;
}
int now=max(0,a[i+1].F.F-a[i].F.F);
now=now/(a[i].F.S-a[i+1].F.S)+1;
if(lef>now){
cout<<-1<<"\n";return;
}
rig=min(rig,now);
}
}
cout<<lef<<"\n";
}
int main(){
int T=1;cin>>T;
while(T--)solve();
}
//a[i]-a[j]<t*(b[j]-b[i])
/*
5
1
7
1
0
2
7 3
4 7
1 0
2
3 6
6 3
0 1
2
7 3
6 8
1 0
2
7 7
8 8
0 1
*/
```
by _qingshu_ @ 2024-04-21 21:28:25