自动搬运

查看原文

来自洛谷，原作者为

	VioletIsMyLove AFO

搬运于2025-08-24 22:21:12，当前版本为作者最后更新于2020-07-31 19:20:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

当我们把脑袋向左旋转90°,把每一个石柱子看成一条线段,把枚举的高度看成一条竖线,唉呀妈呀这不就是传说中的扫描线吗?

此题的细节之处就是需要把高度抽象成一个小方格,换句话说就是把列看成是 $Hi$ 个小积木

Code:

#include<bits/stdc++.h>
#define maxh 500005
using namespace std;
int N,H,Ans,hight[maxh],Sum[maxh];
int read(){
	int ret=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-')f=-f;ch=getchar();}
	while (isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
	return ret*f;
}
int main(){
	N=read(),H=read();
	for (int i=1;i<=N;i++){
		int x=read();
		if (i&1) hight[1]++,hight[x+1]--;else hight[H-x+1]++,hight[H+1]--;
	}
	for (int i=1;i<=H;i++) Sum[i]=Sum[i-1]+hight[i];
	sort(Sum+1,Sum+1+H);
	for (int i=1;i<=H;i++)
	  if (Sum[i]==Sum[1]) Ans++;else break;
	printf("%d %d\n",Sum[1],Ans);
	return 0;
}

但换个角度思考，我们会发现这道题居然还可以用毛毛虫去做，解释在代码里。

Code:

//毛毛虫 
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int N,Ans,Ans_k,H,A[maxn],B[maxn];
int read(){
	int f=1,ret=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f; ch=getchar();}
	while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
	return f*ret;
}
int main(){
	Ans=N=read(),H=read();
	for(int i=1;i<=N;i++)
		if(i&1) A[i+1>>1]=read();	//石笋 
		else	B[i+1>>1]=read();	//石钟乳 
	sort(A+1,A+(N>>1)+1);
	sort(B+1,B+(N>>1)+1);
	int A_l=1,B_l=(N>>1);
	for(int i=1;i<=H;i++){
		while(A[A_l]<i&&A_l<=(N>>1))   A_l++;	//找到第一个需要灭了的石笋 
		while(H-B[B_l]<i&&B_l<=(N>>1)) B_l--;	//找到第一个需要灭了的石钟乳 
		if(N-A_l-B_l+1==Ans) Ans_k++;
		if(N-A_l-B_l+1< Ans) Ans=N-A_l-B_l+1,Ans_k=1;
	}
	printf("%d\n%d\n",Ans,Ans_k);
	return 0;
}

我看到这道题有人写的题解是树状数组，其实我一开始也写的是树状数组，但后来自己一思考发现根本没有写树状数组的必要，题目中根本不需要修改数值，所以还不如写扫描线。最重要的是！！！树状数组时效要慢2倍。。。

树状数组Code:

#include<bits/stdc++.h>
using namespace std;
int n,h,minn,maxn;
int b[2000005],c[5000005];
void put(int x,int v){for(int i=x;i<=h;i+=i&-i)c[i]+=v;}
int get(int x){
	int cnt=0;
	for(int i=x;i;i-=i&-i)cnt+=c[i];
	return cnt;
}
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main(){
	n=read();h=read();
	for(int i=1;i<=n;i+=2){
		int x=read(),y=read();
		put(1,1);put(x+1,-1);put(h-y+1,1);
	}
	for(int i=1;i<=h;i++)b[i]=get(i);
	sort(b+1,b+1+h);
	for(int i=1;i<=h;i++){minn++;if(b[i]!=b[i+1])break;}
	printf("%d %d\n",b[1],minn);
	return 0;
}