[bzoj3141] [HNOI2013]旅行

Description

Input

第一行为两个空格隔开的正整数n, m，表示旅行的城市数与旅行所花的月数。接下来n行，其中第 i行包含两个空格隔开的整数Ai和Bi，Ai表示他第i个去的城市编号。Bi为0或1;如果Bi=0则表示城市Ai没有小L想去的景点，如果Bi=1则表示城市Ai有小L想去的景点，
Ai两两不同且有1<=Ai<=N,即{Ai}为1,2....N的一个排列。
例如{2,1,3,4...N}
N<=500000,M<=200000

Output

t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，为给小L安排的旅行计划对应的路线。为给小L安排的旅行计划对应的路线。

Sample Input

8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0

Sample Output

1 6 8

Solution

由于要计算\(0\)的个数和\(1\)的个数，一个很显然的想法就是把\(0\)改成\(-1\)。

先不管字典序，考虑下答案应该是多少。

显然有这么两条性质：

• 若原数列只由\(1\)或\(-1\)构成，答案显然就是\(\lceil\frac{n}{k}\rceil\)。
• 否则，必定存在一段和为\(0\)的子数列，这段其实没有意义，随便和左边或右边合并都行。

所以可以把\(-1\)或\(1\)消掉一种，然后就变成了第一种情况。

答案就是：
\[ \lceil\frac{|sum[1]|}{k}\rceil? \]
其中\(sum[x]\)为数列的后缀和。

当然有一种特殊情况：上面的式子为\(0\)，但是没有\(k\)个\(sum[x]=0\)的点，显然凑不出\(k\)个和为\(0\)的段，所以这种情况答案是\(1\)。

然后考虑字典序怎么做：

如果答案为\(0\)，单调队列随便搞搞就行了。

否则的话，设上次选的位置为\(l\)，那么这次选的数的后缀和\(s\)显然要满足\(|sum[l]-s|\leqslant ans\)，即\(sum[l]-ans\leqslant s \leqslant ans+sum[l]\)。

所以对于\(sum[x]\)相同的，把他们归为一类处理，然后用单调队列维护就行了。

注意选完这个数之后，后面形成了一个子问题，答案要不大于整个问题的答案，设当前选的数位置为\(x\)，即：
\[ \lceil\frac{|sum[x+1]|}{n-x}\rceil\leqslant ans \]
注意负数下标特别处理，具体看代码。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

const int maxn = 1e6+10;

struct data {int l,r,val;}w[maxn<<2];

int tot;

int n,k,id[maxn],t[maxn],sum[maxn],cnt[maxn];

struct Priority_Queue {
    int st,ed,len;
    int empty() {return !len;}
    void push_back(int x) {
        if(len) w[++tot]=(data){ed,0,x},w[ed].r=tot,ed=w[ed].r;
        else w[++tot]=(data){0,0,x},st=ed=tot;
        len++;
    }
    void pop_back() {ed=w[ed].l,len--;}
    void pop_front() {st=w[st].r,len--;}
    int back() {return w[ed].val;}
    int front() {return w[st].val;}
    void push(int x) {
        while(!empty()&&id[w[ed].val]>id[x]) pop_back();
        push_back(x);
    }
}alpha[maxn<<1],beta[maxn<<2],*q1=alpha+maxn,*q=beta+maxn;  //负数下标处理

int main() {
    read(n),read(k);
    for(int i=1;i<=n;i++) {read(id[i]),read(t[i]);if(!t[i]) t[i]--;}
    for(int i=n;i;i--) sum[i]+=sum[i+1]+t[i];
    for(int i=n;i;i--) cnt[i]=cnt[i+1]+(sum[i]==0);
    cnt[n+1]=-1;
    int ans=sum[1]?(abs(sum[1])+k-1)/k:(cnt[1]<k);
    if(!ans) {
        for(int i=1,j=2;i<k;i++) {
            for(;cnt[j+1]>=k-i;j++) if(!sum[j+1]) q[0].push(j);
            printf("%d ",id[q[0].front()]);q[0].pop_front();
        }
    } else {
        int l=0;id[n+1]=n+1;
        for(int i=2;i<=n;i++) q[sum[i]].push_back(i-1);
        for(int i=1;i<k;i++) {
            int s=n+1;
            for(int j=sum[l+1]-ans;j<=sum[l+1]+ans;j++) {
                if((abs(j)+k-i-1)/(k-i)>ans) continue;
                while(!q[j].empty()&&n-q[j].front()>=k-i) {
                    if(q[j].front()>l) q1[j].push(q[j].front());
                    q[j].pop_front();
                } 
                while(!q1[j].empty()&&q1[j].front()<=l) q1[j].pop_front();
                if(!q1[j].empty()) if(id[s]>id[q1[j].front()]) s=q1[j].front();
            }
            l=s;printf("%d ",id[s]);
        }
    }printf("%d\n",id[n]);
    return 0;
}

[bzoj3141] [HNOI2013]旅行

原文：https://www.cnblogs.com/hbyer/p/10253761.html