alpcOj Journey to the The World's Start

ゝ一世哀愁。 2022-09-23 14:45 22阅读 0赞

题目链接：[http://oj.alpc.cn/en/Problem/Details?cid=17&tid=J][http_oj.alpc.cn_en_Problem_Details_cid_17_tid_J]

Jerry Prince is the fourth grade student and he goes to New-Lodnon to visit the most popular amusement park “The World’s Start”.

An airport he arrives at is next to the first stop of the metro line. This line has n stops and “The World’s Start” is on the last of them. The metro of New-Lodnon is pretty fast so you may assume that you can get from a stop to the next one in just one minute.

题目大意：有从左到右有1-n共n个车站，有n-1种车票，每种票有固定的价钱，每种最多可以坐1-(n-1)站，每个人只能持有一种车票，下车后可以继续上车（每次上车后可以中途下车，但最多做车票对应的站数），但每次下车都要再上车都要花费一定时间，第1和n站上车不花费时间，车从每行进一站需要一分钟，问在t时间内从1-n站话费的票价最低是多少。

解题思路：  
这道题的关键在于如何求每种票到达终点所需的最少时间，如果找出了每种票到车站的最少时间，再直接判断哪种票最便宜就好了。

对于求每种票的时间，最直观的想法是对每一种票进行dp，设dp\[i\]为到i站所需的最少时间，L为此票最多能乘坐的站数，time\[i\]为在此站下车又上车的时间。  
dp\[i\]=min(dp(i-t))+time\[i\] 1<=t<=i-L  
对于n-1种票，每种票枚举n个车站，枚举到每个车站时还要向前推L个，复杂度为n^3

但我们会发现，车票行进距离越大，所需的总时间越小，因为假设n站的最优解（也就是最优停车位置已定），n+1站的车票也能在相应的停车位置停车，反之则不能，所以n+1站一定包含n站最优解。这样我们就可以二分查找所需时间小于等于t-(n-1)的车票就好了。复杂度n^2\*logn

对于每次dp，我们找区间中的最小值时，可以采用单调队列的方法来计算区间最小值，这里因为要根据位置判断是否剔除，所以我在单调区间里保存的是位置，详情见代码。复杂度n\*logn 。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int price[55005];
    int time[55005];
    int que[55005];
    int n,t;
    
    LL dp[55005];
    
    int main()
    {
    
        RII(n,t);
        t-=(n-1);
        LL sum=0;
        for(int i=1; i<n; i++)
        {
            RI(price[i]);
        }
        for(int i=2; i<=n-1; i++)
        {
            RI(time[i]);
            sum+=time[i];
        }
    
        time[n]=0;
    
        int l=1, r=n-1;//车票的站数
    
        while(r-l>1)
        {
            int mid=(r+l)>>1;
    
            int ll=1,rr=0;//单调区间的左值和右值
    
            dp[1]=0;
    
            que[1]=inf;//que数组保存单调区间里的值，注意值是位置
    
            for(int i=2;i<=n;i++)
            {
                //判断是否要剔除单调区间里的值
    
                if(i-que[ll]>mid)  ll++;
    
                //如果新加了一个小值 则向前覆盖
    
                while(rr>=ll&&dp[i-1]<=dp[que[rr]]) rr--;
    
                que[++rr]=i-1;//每次单调区间里的值增加一个
    
                //更新dp[i]
    
                dp[i]=dp[que[ll]]+LL(time[i]);
    
            }
    
            if(dp[n]>t) l=mid;
            else r=mid;
        }
    
        int ans;
    
        //按我的二分方法l==1可能统计不到，这里进行特判
    
        if(sum<=t) {
                ans=price[1];
            r=1;
        }
        else ans=price[r];
    
        for(int i=r+1;i<=n-1;i++)
        {
            ans=min(ans,price[i]);
        }
    
        printf("%d\n",ans);
    
        return 0;
    }

[http_oj.alpc.cn_en_Problem_Details_cid_17_tid_J]: http://oj.alpc.cn/en/Problem/Details?cid=17&tid=J