husky排队吃糖 | 王大神—

Markdown

发布日期: 2021-12-13

更新日期: 2021-12-18

文章字数: 1.7k

阅读次数:

题目描述

有 $K$（$1\le K\le 10^6$）只小 $husky$ 按 $AC$ 题的数量排成一列，等着大 $husky$ 喂糖果，排好队后每只小 $husky$ 获得新编号，从 $1$ 号编到 $K$ 号，大 $husky$ 会将袋中的糖果喂给小 $husky$ 作为 $AC$ 题的奖励。

每次队列最前面的小 $husky$ 可以吃到一块糖果，然后根据小 $husky$ 的习惯（$m_i$）从队尾向队头的方向数 $m_i$ 只小 $husky$，跑到那只小 $husky$ 前面。

举个例子：

初始队列 $1,2,3,4,5,6$，假设第一只小 $husky$ 的习惯（$m_1$）为 $4$, 第二只小 $husky$ 的习惯（$m_2$）为 $1$。

第一只小 $husky$ 的习惯（$m_1$）为 $4$，当 $1$ 号小 $husky$ 奔跑结束后的队列为：$2,1,3,4,5,6$

第二只小 $husky$ 的习惯（$m_2$）为 $1$，当 $2$ 号小 $husky$ 奔跑结束后的队列为：$1,3,4,5,2,6$

第一只小 $husky$ 的习惯（$m_1$）为 $4$，当 $1$ 号小 $husky$ 奔跑结束后的队列为：$3,1,4,5,2,6$

如果习惯 $m_i=0$ 那么，吃完糖就会跑到队尾。

糖果厂家派发糖果时派发了无数包糖果。但是大 $husky$ 正在想今天午饭吃什么，所以每没有注意到有小 $husky$ 没吃到糖果。一些小 $husky$ 永远也吃不到糖果，求最后有几只小 $husky$ 没吃到过糖果。

输入格式

第一行一个 $N$，代表小 $husky$ 的数量。

第二行 $N$ 个数，第 $i$ 个数代表，第 $i$ 只小 $husky$ 的习惯（$m_i$）。

输出格式

一个数，代表没有吃过糖果的小 $husky$ 的数量。

样例

读入 1

5
2 4 0 3 4

输出 1

读入 2

7
5 2 6 6 2 4 5

输出 2

读入 3

15
2 8 1 12 7 7 8 13 2 1 13 13 8 7 7

输出 3

数据范围

$0 \le m_i < N$

情况一（$6$ 分）：$N \le 1000$

情况二（$15$ 分）：$N \le 1e4$

情况三（$57$ 分）：$N \le 1e5$

情况四（$100$ 分）：$N \le 1e6$

情况五（$12$ 分）：$m_i$ 相同（与前几种情况有重合）

题解

弱化：P4090 Greedy Gift Takers P

不难发现，如果前面的小 $husky$ 已经成循环了，就没有后面的小 $husky$ 吃糖果的可能了。

而最后的循环节长度是一定的，所以我们可以找循环节来确定结果。

二分

二分循环节长度，如果枚举的长度中已经有小 $husky$ 吃不到糖果，就说明实际循环长度要更短。

如果循环成功了，那么要尝试更大的循环，有可能有后面的小 $husky$ 也参与循环，但是没有被枚举到。

例如：$0,0,0,0,0$（每只小 $husky$ 的习惯）

枚举循环长度 $1,2,3,4,5$ 都可以满足循环的要求，但是结果循环应该是 $5$。显然所有的小 $husky$ 多可以吃到糖。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
#include<bitset>
using namespace std;
long long r_r(){//快读 
    long long k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
}
const int o_o=1e7+10;
int a_a[o_o];//husky 的习惯 
int b_b[o_o];//临时数组，排序预估循环内的 husky 的习惯 
int n;//husky 的数量 
bool f_i(int k_k){
    for(int i=1;i<k_k;i++) b_b[i]=a_a[i];//复制预估的循环内的 husky 
	sort(b_b+1,b_b+k_k);//按习惯排序 
	int t_p=n-k_k;//预估循环外长度 
	for(int i=1;i<k_k;i++){
		if(b_b[i]>t_p) return 0;//这只小 husky 前面的 husky 已经成循环了，所以轮不到了 
		t_p++;//有 husky 跑到后面了 
	}
	return 1;
}
int main(){
	n=r_r();
	for(int i=1;i<=n;i++)a_a[i]=r_r();//读入小 husky 的习惯 
	int l=1,r=n;
	while(l<=r){//二分循环 
		int m_i=(l+r)>>1;
		if(f_i(m_i))l=m_i+1;//循环要扩大，有可能别的 husky 也参与循环 
		else r=m_i-1;//循环可以更小，已经有 husky 吃不到糖果了 
	}
	printf("%d",n-r);//输出循环节外的 husky（没吃过糖果的） 
	return 0;
}

~~这时已经有 $87$ 分的好成绩了！（而且弱化版已经可以过了！）~~

线段树

二分的复杂度已经满足不了数据了，就要想别的方法了。

刚刚我们二分枚举的是循环节，而循环节是前几只 $husky$ 的习惯造成的，那么我们可以处理前缀！

必须保证这 $k$ 个数都刷新在前 $k$ 个位置里面，并且是第一次，否则会有更早的循环形成。

那么我们每一次让一只 $husky$ 跑走，让所有习惯跑在它后面的 $husky$ 习惯都再往前跑一个，当出现有小 $husky$ 只能跑到队头的时候，说明循环长度找到，结束。而维护前面有几只跑走的小 $husky$ 对后面的 $husky$ 会造成影响就可以用线段树数（或树状数组）来维护。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
#include<bitset>
using namespace std;
long long r_r(){//快读 
    long long k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
}
const int o_o=1e8+10;
int l_l(int k){
	return k<<1;
}
int r_r(int k){
	return k<<1|1;
} 
int n,a_a[o_o];
struct po{
	int m_i;//最多能跑到多靠前 
	int l_n;//有几只 husky 跑到前面的懒标记 
}t_r[o_o];
void p_d(int x){//释放懒标记 
	t_r[l_l(x)].m_i-=t_r[x].l_n;
	t_r[r_r(x)].m_i-=t_r[x].l_n;
	t_r[l_l(x)].l_n+=t_r[x].l_n;
	t_r[r_r(x)].l_n+=t_r[x].l_n;
	t_r[x].l_n=0;
}
void u_p(int x){
	t_r[x].m_i=min(t_r[l_l(x)].m_i,t_r[r_r(x)].m_i);//记录跑的靠前的 
}
void b_t(int x,int l,int r){
	if(l==r){
		t_r[x].m_i=n-l+1;//直接记录小 husky 会跑到第几位 
		return;
	}
	int m_i=(l+r)>>1;
	b_t(l_l(x),l,m_i);
	b_t(r_r(x),m_i+1,r);
	u_p(x);
}
void a_d(int x,int l,int r,int v){
	if(l>v)return;//超出范围 
	if(r<=v){//在这只小 husky 习惯的前面 
		t_r[x].m_i--;//更新能跑到的最前位置 
		t_r[x].l_n++;//懒标记 
		return;
	}
	int m_i=(l+r)>>1;
	p_d(x);//释放懒标记 
	a_d(l_l(x),l,m_i,v);
	a_d(r_r(x),m_i+1,r,v);
	u_p(x);//更新节点 
}
int main(){
	n=r_r();
	for(int i=1;i<=n;i++)a_a[i]=r_r()+1;//记录 husky 的习惯 
	b_t(1,1,n);//建树 
	for(int i=1;i<=n;i++){//枚举每只小 husky 
		a_d(1,1,n,a_a[i]);//小 husky 跑走 
		if(t_r[1].m_i<=0){//出现循环 
			printf("%d\n",n-i);
			return 0;
		}
	}
	return 0;
}