题解 P6481 【[CRCI2006-2007] FIREFLY】

· · 题解

当我们把脑袋向左旋转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;
}