题解：P7057 [NWRRC2015] Journey to the “The World’s Start”

Your_Name · 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;
}

完结撒花。