Noble 的博客

Noble 的博客

♡虹蓝♡

题解 【卢卡杨比火车站/(Nescafé杯模拟赛一)星之船】

posted on 2019-07-10 20:44:53 | under 未分类 |

好像是学校祖传老题来着。

据说这题原题最早是毕克毕姥爷出的。原题来自雀巢咖啡杯第一场,确实是个老题原题link

题面:

您被分配到了火车司机的岗位,尽管您想当文艺工作者,您的任务是去运载被肃反的老布尔什维克,并将他们流放到西伯利亚,因为“要么跟约瑟夫走,要么跟弗拉基米尔走”,尽管工业化的路线是约瑟夫从列夫那里照搬过来的,然而由于列夫被驱逐,去了墨西哥,所以工业化的细节并不优秀,也不够灵活,导致您的火车的车门位置是乱的。

我们可以认为卢卡扬比火车站的站台长度是 L,火车最左侧的门称为第 1 个门,对于满足 1 ≤ I ≤ N 的整数,火车的第 i 个门与第 1 个门之间的距离是 Di ,并且 有 0 = D1 < D2 <...< DN-1 < DN ≤ L。站台上有 M 个乘客,对于满足 1 ≤ I ≤ M 的整数,第 i 个乘客距离站台左边缘的距离为 Pi ,那么有 0 ≤P1 ≤ P2 ≤ … ≤ PM ≤ L。如果火车停在 S 这个位置,也就是说火车的第 1 个门正对着站台的位置距离站台左边缘的距离是 S,那么由于所有的门都要正对站台,显然有 0 ≤ S ≤ L - DN 。此时,火车的第 i 个门正对站台的位置就是 S + D i 。

如果第 i 个乘客从第 j 个门上车,由于火车站巨大(因为有大量人员需要被流放),门的大小可以忽略不计,那么他需要走的距离就是|Dj + S - Pi |。当然,所有的乘客都会选择需要时间最小的门上车。NKVD向您通报了停靠站台的情况,因为您被要求让乘客尽可能多走路,请你上报使得所有乘客上车距离和最长的停靠位置 S,以及此时所有乘客上车所需的距离总和。

如果存在多种满足条件的停靠方式,请输出S最小的方案。

题面latex炸了,领会精神。

数据范围

对于 30%的数据 L ≤ 100; M ≤ 50; N ≤ 50。

对于 100%的数据 0< L ≤10,0000,0000; M ≤ 300; N ≤ 300。


苏联笑话永不过时。 看在慈父面子上不上原题面了,反正原题面也没啥意思,感兴趣可以去开头链接自己看。

好像能说的比赛时候都写在代码开头了。。。

/*
对于每个人,每次对应一个门。
随着s单调变化,对应的门编号单调递减,所以最多有nm种对应关系 。
考虑上人在门的那个方向,这个也是单调的,又多n种情况。 

这东西的答案是个分段函数,最多2nm段。

分段函数变化的时候至少有一个对应关系发生变化,对应关系发生变化的条件是个关于s的不等式,可以直接移项求每个对应关系变化时最小的s。

然后扔到堆里,每次取最小的s,算答案,修改对应状态就ojbk了

算答案的话,分段函数自变量只有一个次数为1的s,根据斜率求最值就行了。
当然也可以直接带入两个端点取max(当时傻了没想到)

然而考场出锅了,炸了一个int,然后整道题都炸了,100->30

行8,我先离开人世了。

考场rush的代码,还是建议看文字领会精神。
*/
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int kmaxn=300+15;
ll dwlx[kmaxn];//达瓦里希
ll glg[kmaxn];//古拉格
ll Len;
ll ans;
ll anss;
int n,m;
struct Status{
    int pr;
    int dir;//0 left   1 right or direct//门在人的左/右侧 
};
enum DIRECTION{
    L,R
};
Status st[kmaxn];
priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q;//所需s值,前进至下一个状态的同志的编号。 
ll myabs(ll l)
{
    return l>0?l:-l;
}
int lb(ll v)
{
    return lower_bound(glg+1,glg+n+1,v)-glg;
}
ll dir_advance(int p)
{
    ll d=glg[st[p].pr];
    return myabs(dwlx[p]-d)+1;
}
ll sts_advance(int p)
{
    if(st[p].pr<=1)return Len-glg[n]+1;
    ll x=dwlx[p];
    ll a=glg[st[p].pr-1];
    ll b=glg[st[p].pr];
    return (2*x-a-b+1)/2;
}
ll sadvance(int p)
{
    if(st[p].dir==L)
        return dir_advance(p);
    else
        return sts_advance(p);
}
ll cal_num,cal_mul;//常数项,s的系数
void do_advance(int p)
{
    ll d=glg[st[p].pr];//这个d考试时候是int,然后就爆了 
    if(st[p].dir==L)//dir change
    {
        cal_num+=d;
        cal_num-=dwlx[p];
        cal_mul++;
        st[p].dir=R;
        cal_num+=d;
        cal_num-=dwlx[p];
        cal_mul++;
    }
    else//pair change
    {
        st[p].dir=L;
        cal_num-=d;
        cal_num+=dwlx[p];
        cal_mul--;
        d=glg[--st[p].pr];
        cal_num-=d;
        cal_num+=dwlx[p];
        cal_mul--;
    }
    ll t=sadvance(p);
    q.push(make_pair(t,p));
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>Len>>m;
    Len*=10;
    for(int i=1;i<=m;++i)
    {
        cin>>dwlx[i];
        dwlx[i]*=10;
    }
    cin>>n;
    for(int i=2;i<=n;++i)
    {
        cin>>glg[i];
        glg[i]*=10;
    }
    ll t1,t2;
    int p;
    for(int i=1;i<=m;++i)//求初始配对 
    {
        t1=t2=Len*m;
        p=lb(dwlx[i]);
        if(p<=n)//right or direct
            t1=myabs(glg[p]-dwlx[i]);
        --p;
        if(p>0)//left 
            t2=myabs(glg[p]-dwlx[i]);
        if(t1<t2)//dwlx glg
        {
            st[i].dir=R;
            st[i].pr=p+1;
            cal_num+=glg[p+1];
            cal_mul++;
            cal_num-=dwlx[i];
        }
        else//glg dwlx
        {
            st[i].dir=L;
            st[i].pr=p;
            cal_num-=glg[p];
            cal_mul--;
            cal_num+=dwlx[i];
        }
    }
    for(int i=1;i<=n;++i)//求每个点状态前进所需的s. 
    {
        t1=sadvance(i);
        q.push(make_pair(t1,i));
    }
    ////初始状态答案
    ans=0;
    t1=0;
    t2=q.top().first-1; 
    ll tans,nows;
    if(cal_mul>0)
        nows=t2-1;
    else
        nows=t1;
    tans=cal_mul*nows+cal_num;
    if(tans>ans){
        ans=tans;
        anss=nows;
    }
    while((t1=q.top().first)<=Len-glg[n])//range [t1,t2]
    {
        p=q.top().second;
        q.pop();
        while((t2=q.top().first)==t1)//same
        {
            do_advance(p);
            p=q.top().second;
            q.pop();
        } 
        do_advance(p);
        if(cal_mul>0)
            nows=t2-1;
        else
            nows=t1;
        tans=cal_mul*nows+cal_num;
        if(tans>ans){
            ans=tans;
            anss=nows;
        }
    }
    cout<<anss/10<<'.'<<anss%10<<' '<<ans/10<<'.'<<ans%10<<endl;
    return 0;
}

/*
样例
4
5
0 1 2 3 4
4
1 2 3
输出
0.5 2.5
*/

时间复杂度nmlog(nm),约等于n^2logn,上界比较松。

出题的说std是n^3的。

using namespace std;
int main(){}
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>

const double eps=1e-1;
struct _Main{
typedef long long ll;

template <typename Type>
void read(Type &a){
    char t;
    while(!isdigit(t=getchar()));
    a=t-'0';
    while(isdigit(t=getchar())) {
        a*=10;
        a+=t-'0';
    }
}
double left;
double ans[2];
double calc(){
    double ret=0;
    int i,j,k;
    j=0;
    for(i=0;i<m;i++){
        while(j+1<n && fabs(d[j+1]+left-p[i])<fabs(d[j]+left-p[i])){
            j++;
        }
        ret+=fabs(d[j]+left-p[i]);
    }return ret;
}

int l,m,n;
int p[305],d[305];
_Main(){
    double temp;
    int i,j,k;
    read(l);
    read(m);
    for(i=0;i<m;i++){
        read(p[i]);
    }
    read(n);
    for(i=1;i<n;i++){
        read(d[i]);
    }
    left=0;
    ans[0]=calc();
    ans[1]=left;

    left=l-d[n-1];
    temp=calc();
    if(temp>ans[0]){
        ans[0]=temp;
        ans[1]=left;        
    }

    for(i=1;i<n;i++){
        for(j=0;j<m;j++){
            left=p[j]-(d[i]-d[i-1])/2.0-d[i-1];
            if( left>-eps && (left +d[n-1]  < l+eps )){
                temp=calc();
                if(temp>ans[0]+eps || ((temp>ans[0]-eps) && left<ans[1]-eps)){
                    ans[0]=temp;
                    ans[1]=left;        
                }
            }
        }
    }
    printf("%.1lf %.1lf",ans[1],ans[0]);
    fclose(stdout);
}   

}boat;
//反正出题人给的std就是这个,这是个什么东西我也不知道,我也不敢问。
//也不知道能不能运行。

网上唯一的一篇题解链接,可能也是n^3的(并不确定)。

不知道之前有没有n^2logn做法,按照出题人(并不是毕克)的反应,可能是没有。

回头试试卡掉n^3算法把这题再出一遍。

仔细研究了这个优化的原理,准备把总用时最大出成最小值最大/最大值最小。然后卡掉n^3。