蓝桥杯周赛 第 1 场 强者挑战赛 6. 小球碰撞【算法赛】(思维题/最长上升子序列LIS)

题目

https://www.lanqiao.cn/problems/9494/learning/?contest_id=153

思路来源

Aging代码

题解

二分时间t，第i个小球对应一个起点pi、终点pi+t*vi的区间，问题转化为，

选最多的区间，使得不存在区间包含（即li<lj<rj<ri）的情况，

如果可以选这样的区间>=n-k个，则t是合法的时间

由于左端点均不同，所以先按左端点排序，

排完序后，考虑右端点的LIS，如果>=n-k，即合法，否则不合法

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
const ll INF=8e18;
int t,n,k,p[N],v[N];
P a[N];
ll b[N];
bool ok(int T){
	rep(i,1,n){
		a[i]=P(p[i],1ll*v[i]*T+p[i]);
	}
	sort(a+1,a+n+1);
	fill(b,b+n+1,INF);
	rep(i,1,n){
		ll x=a[i].se;
		//printf("T:%d i:%d x:%lld\n",T,i,x);
		(*lower_bound(b,b+n+1,x))=x;
	}
	int p=lower_bound(b,b+n+1,INF)-b;
	//printf("T:%d p:%d\n",T,p);
	return p>=n-k;
}
void sol(){
	sci(n),sci(k);
	rep(i,1,n){
		sci(p[i]),sci(v[i]);
	}
	int l=1,r=2e9+1;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(ok(mid))l=mid+1;
		else r=mid-1;
	}
	if(r<=2e9)pte(r);
  else puts("-1");
}
int main(){
	t=1;
	//sci(t); // t=1
	while(t--){
		sol();
	}
	return 0;
}