https://www.cnblogs.com/hua-dong/p/9460761.html
思路二分假设地铁卡能走的最短的距离，找到这个最小值后，往大于等于这个距离的卡看，取其中的最小值，即为答案。
二分出距离，要判断用这个距离的卡，能否在规定时间内到达终点，这里用单调队列优化dp,时间复杂度为O（nlogn）
代码#include <bits/stdc++.h> using namespace std; typedef long long ll; ll price[100010];//price[i]表示 能走的距离的最大值为i的票的价格 ll minute[100010];//进入该第i个地铁站所花费的时间 ll dp[100010];//dp[i]指花费的时间 ll que[100010];//单调队列 ll head,tail;//队列的头下标和队列的尾下标 ll n,t;//地铁站的个数，容许花费的最大时间。 bool check(ll L) {head=1,tail=1;//头尾都是1que[head]=1;dp[1]=0;//单调队列的基本操作for(int i=2;i<=n;i++)//遍历每一个距离{while(tail<head && i-que[tail]>L)//当 i 到尾的距离大于假定的最短距离 ，尾往前走tail++;dp[i]=dp[que[tail]]+minute[i];//来到上一个位置（尾）所花费的时间加上到i花费的时间que[++head]=i;//在队列中加入当前地铁站while(tail<head && dp[que[head]]<=dp[que[head-1]])// 维护单调队列，将头后比头大的弹掉，直到从尾到头是单调递增的。{que[head-1]=que[head];head--;}}return dp[n]<=t;//如果花费的时间比给的时间小，那么再往更小的距离所在的区间搜 ，r=mid-1; } int main() {/* 二分出L,L是卡能走的最短的间隔距离， 然后在>=L里选择一个最低价格即可 二分里面用单调队列优化 复杂度O(NlogN).*///freopen("journey.in", "r", stdin);//freopen("journey.out","w",stdout);scanf("%lld %lld",&n,&t);t-=n-1;for(int i=1;i<=n-1;i++)scanf("%lld",&price[i]);for(int i=2;i<=n-1;i++)scanf("%lld",&minute[i]);ll l=1,r=n-1,mid,mn;//mn是L的最小值while(l<=r)//用二分求出最小距离{mid=(l+r)/2;if(check(mid))//用单调队列优化{mn=mid;r=mid-1;}elsel=mid+1;}ll ans=price[mn];for(int i=mn+1;i<n;i++)ans=min(price[i],ans);printf("%lldn",ans);return 0; }
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
