自动搬运

查看原文

来自洛谷，原作者为

	Your_Name 君の名前は？

搬运于2025-08-24 22:26:15，当前版本为作者最后更新于2025-01-18 19:18:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

首先，考虑一个事实，即当一个 $r$ 满足条件时，那么比他大的所有车票也一定满足条件。证明显然，因为大的票本来就严格包含小的票，即可以当小的用且所用时间可能更优。由此，单调性有了，那么就可以二分了。

然后，题目说可以往回走，其实显然是不优的，于是我们设计一个显然的 dp。

设 $f_i$ 表示经过前面 $i - 1$ 个星球到 $i$ 这个星球的最小花费。

转移：

发现本质上还是滑动窗口，直接单调队列解决。

注意，他会把 $n$ 个星球都走一遍，时间最少也要 $n-1$，所以我们一开始把他减掉就行。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
LL n, a[N], w[N], t, ans = 1e18, f[N];
deque<LL>q;
bool check(LL x){
    q.clear();
    q.push_back(1);
    for(LL i = 2; i <= n; i ++){
        while(!q.empty() && q.front() < i - x)q.pop_front();
        f[i] = f[q.front()] + w[i];
        while(!q.empty() && f[q.back()] >= f[i])q.pop_back();
        q.push_back(i);
    }
    return f[n] <= t;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> t;
    t -= n - 1;
    for(LL i = 1; i < n; i ++){
        cin >> a[i];
    }
    for(LL i = 2; i < n; i ++){
        cin >> w[i];
    }
    LL l = 1, r = n - 1, mid;
    while(l < r){
        mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }//二分第一个满足条件的
    for(LL i = l; i < n; i ++){
        ans = min(ans, a[i]);
    }//后面都满足条件
    cout << ans;
    return 0;
}

完结撒花。