自动搬运

查看原文

来自洛谷，原作者为

	是个汉子 世人万千种，浮云莫去求。斯人若彩虹，遇上方知有。

搬运于2025-08-24 21:46:43，当前版本为作者最后更新于2020-11-22 10:58:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷传送门

这个题用到了单调队列的优化，但是精髓绝不止在于此。+_+

Solution

我们先不管字典序怎么办，想想怎么求最小的 $ans$

首先，因为要的是绝对值，那么考虑将 $0$ 化为 $-1$ ，也就是将没有景点的城市看作会减少一个景点的城市（雾

设 $b_i$ 表示城市 $a_i$ 是否有景点，有为 $1$ ，否则为 $-1$，$sum_{i}$ 表示 $i+1$ 到 $n$ 的后缀和，也就是 $sum_{i}=b_{i+1}+b_{i+2}+\cdots+b_n$ ，那么可以证明答案最小不小于 $\lceil \frac {|sum_0|}m\rceil$ 。

如果全部是 $1$ 或 $-1$ ，显然平均的将 $sum_0$ 分为 $m$ 份最好；如果同时有 $1,-1$ ，将相邻的两个 $1,-1$ 合并可以得到 $0$ 即抵消，最后还是剩下 $sum_0$ 个 $1$ 或 $-1$ ，就和第一种一样了。

但是还是有一种特殊情况的，当 $sum_0=0$ 且 $sum_i=0$ 的 $i$ 的数量不足 $m$ 个，此时答案就是 $1$ ，因为分不了那么多段。

既然 $ans$ 已经能够求出来了，那么就可以回来看看字典序

将 $ans=0$ 和 $ans\not =0$ 分开考虑。

当 $ans=0$ 时，即 $sum_0=0$ 并且 $sum_i=0$ 的 $i$ 的数量 $\geq m$ ，那么就在这些 $i$ 中跑一遍单调队列即可。

再具体就是维护队列里 $a_i$ 从小到大，按照输入顺序入队 ，找到字典序最小的 $m-1$ 个。（因为第 $m$ 个城市必定是 $a_n$ ）

当 $ans\not= 0$ 时，我们假设第 $i$ 段结尾的是 $lst$ ，那么 $i+1$ 段的结尾后一个位置的后缀和 $s$ 需要满足 $|sum_{lst}-s|\leq ans\Rightarrow sum_{lst}-ans\leq s\leq sum_{lst}+ans$ 。

那么选择按 $sum_i$ 分类，对每一种 $sum_i$ 开一个单调队列，维护队列里 $a_i$ 单调递增，选的时候从 $sum_{lst}-ans$ 到 $sum_{lst}+ans$ 枚举选择，注意我们还需要判断 $\lceil \frac {|s|}{m-i}\rceil\leq ans$ 。

注意：这题卡空间，所以要手动写队列。(●ˇ∀ˇ●)

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define B N

using namespace std;
const int N=500010;

template<typename T>void read(T &x){
    x=0;bool f=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    if(f) x=-x;
}

struct node{
    int v,id;
};
int cnt;
struct Node{
    node p;
    int pre,nxt;
}tr[N<<1];
int newcode(node p,int pre,int nxt){tr[++cnt]=(Node){p,pre,nxt}; return cnt;}

struct queue{
    int siz,hd,tl;
    bool empty(){return !siz;}

    void push_front(node p){
        if(!siz) hd=tl=newcode(p,0,0);
        else tr[hd].pre=newcode(p,0,hd),hd=tr[hd].pre;
        ++siz;
    }

    void push_back(node p){
        if(!siz) hd=tl=newcode(p,0,0);
        else tr[tl].nxt=newcode(p,tl,0),tl=tr[tl].nxt;
        ++siz;
    }

    void pop_front(){siz--,hd=tr[hd].nxt;}
    void pop_back(){siz--,tl=tr[tl].pre;}

    node front(){return tr[hd].p;}
    node back(){return tr[tl].p;}
}q[N<<1];

int tot,head[N<<1],nxt[N<<1];
node to[N<<1];
void add(int u,node p){
    to[++tot]=p;
    nxt[tot]=head[u];
    head[u]=tot;
}

int n,m,lst,ct[N],sum[N],rest[N];//rest表示休息点的后缀和 sum表示相加的后缀和
int calc(){
    int ans=0;
    for(int i=n;i>=1;i--){
        if(!sum[i]) ans++,rest[i]=1;
        rest[i]+=rest[i+1];
    }
    if(ans>=m) return 0;
    else return 1;
}

void push(int u,node p){
    while(!q[u].empty()&&p.v<q[u].back().v) q[u].pop_back();
    q[u].push_back(p);
}

node calc(int u,int lim){
    for(int i=head[u];i&&to[i].id<=lim;i=nxt[i]) push(u,to[i]),head[u]=i;
    while(!q[u].empty()&&q[u].front().id<=lst) q[u].pop_front();
    return q[u].empty()?(node){N,N}:q[u].front();
}

node min(node a,node b){return a.v<b.v?a:b;}

int main(){
    read(n); read(m);
    for(int i=1;i<=n;i++) read(ct[i]),read(sum[i-1]),sum[i-1]=(sum[i-1])?1:-1;
    for(int i=n-1;i>=0;i--) sum[i]+=sum[i+1];
    for(int i=n;i>=1;i--) add(sum[i]+B,(node){ct[i],i});
    int S=sum[0],d=(S!=0)?(int)ceil(1.0*abs(S)/(1.0*m)):calc();
    if(d){
        for(int i=1;i<m;i++){
            node ans=(node){N,N};
            for(int j=S-d+B;j<=S+d+B;j++){
                if(ceil(abs(1.0*j-B)/(1.0*m-i))<=d) ans=min(ans,calc(j,n-(m-i)));
            }
            printf("%d ",ans.v);
            lst=ans.id,S=sum[lst];
        }
    }
    else{
        for(int j=1,i=head[B];j<m;j++){
            for(;i&&rest[to[i].id]-1>=m-j;i=nxt[i]) push(B,to[i]);
            printf("%d ",q[B].front().v);
            q[B].pop_front();
        }
    }
    printf("%d\n",ct[n]);
    return 0;
}