题目分析

首先把所有等于0的b值改为等于-1,然后设$s_i$表示从i开始的b的后缀和。

1.对于$s_1=0$且$s_i=0$的i的数量大于等于m个的情况,显然答案是0,方案就用一个单调队列扫一遍就知道了。

2.对于$s_1=0$且$s_i=0$的数量小于m的情况,ans=1。否则,$ans=\lceil \frac{abs(s_1)}{m} \rceil$。

​ 以$s_1$是正数为例,从$s_n$到$s_1$,$1,2,3…s_1$这些值一定都出现过,负数的情况类似,所以此结论成立。

​ 以此出发,我们可以知道,假设我们现在要在k到n之间寻找一个决策点x,作为第i个休息站,那么x一定要满足以下三个条件:

​ 2-1.$abs(s_{k+1}-s_{x+1}) \leq ans$

​ 2-2.$\lceil \frac{abs(s_{x+1})}{m-i} \rceil \leq ans$

​ 2-3.$m-i \leq n-x$

​ 开很多单调队列,其中第t个队列里存的都是满足$s_{x+1}=t$的$x$ ,对于第一个条件,我们只需要在第$s_{k+1}-ans$个队列到第$s_{k+1}+ans$个队列中操作即可。对于第二个条件,我们枚举到一个队列时,判断以下其是否符合条件即可。对于第三个条件,按照从小到大的顺序,边操作边把满足它的$x$值插入单调队列即可。

代码

代码借鉴了这位大神的。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int a[N],b[N],js[N];
int n,m,SZ;
struct node{int pre,nxt,v;}t[N<<1];
struct orzxzy{//单调队列
    int he,ta,len;
    void pop_tail() {ta=t[ta].pre,--len;}
    void pop_head() {he=t[he].nxt,--len;}
    void init(int x) {
        ++SZ,t[SZ].v=x,t[ta].nxt=SZ,t[SZ].pre=ta;
        if(!len) he=SZ;
        ++len,ta=SZ;
    }
    void push(int x) {
        while(len&&a[t[ta].v]>a[x]) pop_tail();
        init(x);
    }
}q[N<<1],p[N<<1];
int cel(int x,int y) {return (x%y==0?x/y:x/y+1);}
void work2() {
    int ans=(b[1]?cel(abs(b[1]),m):1);
    for(int i=1;i<n;++i) p[b[i+1]+n].init(i);
    int las=0;
    for(int i=1;i<m;++i) {
        int mi=n+1,bj=0;
        for(int j=b[las+1]-ans;j<=b[las+1]+ans;++j) {//枚举区间
            if(cel(abs(j),m-i)>ans) continue;//第二个条件
            int kl=j+n;
            while(p[kl].len&&t[p[kl].he].v<=las) p[kl].pop_head();
            while(q[kl].len&&t[q[kl].he].v<=las) q[kl].pop_head();//不能比上一次的值还小
            while(p[kl].len&&n-t[p[kl].he].v>=m-i)//第三个条件
                q[kl].push(t[p[kl].he].v),p[kl].pop_head();
            if(q[kl].len&&a[t[q[kl].he].v]<mi)//取出队首元素,判断
                mi=a[t[q[kl].he].v],bj=t[q[kl].he].v;
        }
        las=bj,printf("%d ",mi);
    }
}
void work1() {
    for(int i=1,j=1;i<m;++i) {
        for(;j<=n&&js[j+1]>=m-i;++j)
            if(!b[j+1]) q[0].push(j);
        printf("%d ",a[t[q[0].he].v]),q[0].pop_head();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]);
    for(int i=n;i>=1;--i)
        b[i]=b[i+1]+(b[i]?1:-1),js[i]=js[i+1]+(b[i]==0);
    if(!b[1]&&js[1]>=m) work1();
    else work2();
    printf("%d ",a[n]);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *