网站名称怎么收录,学做网站论坛教程,网站在线留言系统,鞍山信息港招聘题目
https://www.lanqiao.cn/problems/9494/learning/?contest_id153 思路来源
Aging代码
题解
二分时间t#xff0c;第i个小球对应一个起点pi、终点pit*vi的区间#xff0c;问题转化为#xff0c;
选最多的区间#xff0c;使得不存在区间包含#xff08;即lil…题目
https://www.lanqiao.cn/problems/9494/learning/?contest_id153 思路来源
Aging代码
题解
二分时间t第i个小球对应一个起点pi、终点pit*vi的区间问题转化为
选最多的区间使得不存在区间包含即liljrjri的情况
如果可以选这样的区间n-k个则t是合法的时间
由于左端点均不同所以先按左端点排序
排完序后考虑右端点的LIS如果n-k即合法否则不合法
代码
#includebits/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 pairint,ll P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1e510;
const ll INF8e18;
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]*Tp[i]);}sort(a1,an1);fill(b,bn1,INF);rep(i,1,n){ll xa[i].se;//printf(T:%d i:%d x:%lld\n,T,i,x);(*lower_bound(b,bn1,x))x;}int plower_bound(b,bn1,INF)-b;//printf(T:%d p:%d\n,T,p);return pn-k;
}
void sol(){sci(n),sci(k);rep(i,1,n){sci(p[i]),sci(v[i]);}int l1,r2e91;while(lr){int midl(r-l)/2;if(ok(mid))lmid1;else rmid-1;}if(r2e9)pte(r);else puts(-1);
}
int main(){t1;//sci(t); // t1while(t--){sol();}return 0;
}
