P3697题解

· · 题解

P3697

前言

一道学校比赛的题，弄发双倍经验。

赛时想到是贪心，写一半发现写不下去。细节挺多。

另，后来发现的，AT_joi2017ho_b，注意加换行。

思路

贪心。

首先，不加快车时，能到达的车站应跟在特急车停的站之后。即对于 s_i 和 s_{i+1} 之间的 j，如果 j 可以到达，从 s_i 到 j 的站都符合条件。

再考虑快车。

对于一个站，最快的到达方式是：先坐特急车到最近的站点，再坐快车到最近的站点，最后转慢车。这样 m 个特急车停靠的站点将整条线路分成 m-1 段，分别处理。

在一段之内，从 s_i 出发只坐慢车最远可以到 pos_1,自身贡献 pos_1-s_i+1 个站。如果要在这一段增设快车站，最优是设在 pos_1+1 处，最远能到 pos_2，贡献 res_2 是 pos_2-pos_1。以此类推。直到有 pos_k \ge s_{i+1} 为止。

这样，每段会有一定数量的可以设快车站的点，分别有一定贡献。用优先队列，选出前 k 大贡献即可。

实现

思路好想，实现难些。

注意：

于是就写了一发：

int n,m,k,a,b,c,t;
int pos,res,flag,ans;
int s[maxn];
priority_queue <int> q;

signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    k-=m;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&t);
    for(int i=1;i<=m;i++)scanf("%lld",&s[i]);
    for(int i=1;i<m;i++){
        pos=s[i];flag=0;
        while(pos<s[i+1]){
            if(t-(s[i]-1)*b-(pos-s[i])*c<0)break;
            res=(t-(s[i]-1)*b-(pos-s[i])*c)/a+1;
            if(pos+res>=s[i+1]){
                res=s[i+1]-pos;
                pos=s[i+1];
            }
            pos+=res;
            if(!flag){
                ans+=res;
                flag=1;
            }
            else    q.push(res);
        }
    }
    if(t>=(n-1)*b)ans++;
    while(!q.empty() && k){
        k--;
        ans+=q.top();
        q.pop();
    }
    printf("%lld",ans-1);
}

80分。MLE。

一组数据：

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

在这里，会找出 1000000000 个贡献为 1 的点并入队。显然，后面是不需要那么多的。

又可以发现，在 每一段中，设置车站的贡献单调不增。所以，对于每一段，只需要入队前 k 个贡献。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=30010;

int n,m,k,a,b,c,t;
int pos,res,cnt,ans;
int s[maxn];
priority_queue <int> q;

signed main(){
    scanf("%lld%d%d",&n,&m,&k);
    k-=m;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&t);
    for(int i=1;i<=m;i++)scanf("%lld",&s[i]);
    for(int i=1;i<m;i++){
//      cout<<i<<" "<<s[i]<<endl;
        pos=s[i];cnt=0;
        while(pos<s[i+1]){
            ++cnt;
            if(t-(s[i]-1)*b-(pos-s[i])*c<0)break;
            res=(t-(s[i]-1)*b-(pos-s[i])*c)/a+1;
            if(pos+res>=s[i+1]){
                res=s[i+1]-pos;
                pos=s[i+1];
            }
            pos+=res;
            if(cnt==1){
                ans+=res;
//              cout<<ans<<endl;
            }
            else{
                q.push(res);
//              cout<<res<<endl;    
            }
            if(cnt>k+1)break;
//          cout<<res<<" "<<pos<<endl;
        }
    }
    if(t>=(n-1)*b)ans++;
//  cout<<ans<<endl;
    while(!q.empty() && k){
        k--;
        ans+=q.top();
        q.pop();
//      cout<<ans<<endl;
    }
    printf("%lld",ans-1);
}