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

本文主要是介绍蓝桥杯周赛 第 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=1while(t--){sol();}return 0;
}

这篇关于蓝桥杯周赛 第 1 场 强者挑战赛 6. 小球碰撞【算法赛】(思维题/最长上升子序列LIS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---