题解 P2058 【海港】

看到大佬们的题解思路这么nb,蒟蒻表示并没有看懂= =。于是蒟蒻决定提供一种新思路：

我们注意到数据范围，发现二维数组并不可取，但是我们又注意到∑ki≤3∗105$\sum k_i\le 3\ast {10}^5$，所以采取一种新的思想:将所有人都读在一个一维数组里面：使用一个队列q$q$来存储第i$i$艘船上人数的范围，即q$q$存储的是两个数[l,r]$[l,r]$，其中表示第i$i$艘船上的人从l$l$开始，从r$r$结束。

这是基本存储思想，接下来我们来讲算法：

定义一个map$map$类型m$m$,用来记录当前86400秒内每种国家有多少人。并且我们知道，如果第x$x$艘船的抵达时间已经比第y$y$艘船的抵达时间超过了86400秒，那么还未抵达的船的抵达时间也肯定超过了第y$y$艘船86400秒，因此我们可以开一个变量ft,用来表示当前距离第i$i$艘船小于86400秒且编号最小的船的编号。那么这就是基本的框架。

但是，这样还是会有坑点:

• 如果数组是从1开始开的话，ft一开始必须设置为1，因为一开始默认是第一艘船。

• 假设前面已经有x$x$个人了，队列q$q$放入元素时应该是放入x+1,x+k$x+1,x+k$我被这点坑了好久= =。为什么呢？第一个元素的编号x+1$x+1$,这点毫无疑问，但是，最后一个元素的编号为x+1+k−1=x+k$x+1+k-1=x+k$，很多时候会不自觉的放入x+1,x+k+1$x+1,x+k+1$，于是就会出问题。

• 如果一艘船的抵达时间与现在这艘船的差时刚好是86400秒的话，也不能将此船计算在内。

话不多说，上代码

#define MAXN  300001 //定义最大值
#define MAXN1 100001
using namespace std;
int n,i,j,k,x,ft,t2,h;
int gj[MAXN],t[MAXN1];
map<int,int> m;
queue<pair<int,int> > q;
inline int read(){//快速输入
    int f=1,x=0;
    char c;
    c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
inline void write(int x){//快速输出
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x/10>0) write(x/10);
    putchar(x%10+48);
}
int main(){
    n=read();ft=1;//输入n,并将符合条件的最小的船的编号设置为1
    for(i=1;i<=n;i++){
        t[i]=read();k=read();//输入第i艘船抵达的时间和人的数量
        q.push(make_pair(t2+1,t2+k));//放入第i艘船的人的数量的区间
        for(j=1;j<=k;j++){
            t2++;
            gj[t2]=read();//输入
            if(m[gj[t2]]==0) h++; //如果之前没有该国家的人，计数器+1
            m[gj[t2]]++;//将该国家的人的数量+1
        }
        while(t[i]-t[ft]>=86400){//若不满足条件
            int xa=q.front().first;
            //取出q数组存放的之前满足条件的最小的船的人数的最左下标l
            int ya=q.front().second;
           //取出q数组存放的之前满足条件的最小的船的人数的最右下标r 
            for(j=xa;j<=ya;j++){
                m[gj[j]]--;//将人数-1
                if(m[gj[j]]==0) h--;//若该国没有人了，计数器-1
            }
            q.pop();//释放队列
            ft++;//看下一个船满不满足条件
        }
        write(h);//输出
        cout << endl;
    }
}