解题报告 P2058 海港

题目内容

P2058

大意：计算n条信息。对于输出的第i条信息，你需要统计满足 t_i-86400<t_p \le t_i 的船只 p ，在所有的 x_{p,j} 中，总共有多少个不同的数。

解题思路

对于线性的这种东西，可以使用队列求解。将人的国籍和时间封装成一个结构体，构造结构体队列求解。然后统计答案采用桶排序的思想，开数组w[i]记录第i个国家的人数。具体见代码

代码细节：
– 适当利用自增运算符可以巧妙压行
– 时间等于t_i-86400的人也要被弹出，一开始没注意这个问题WA了好多点然后70分

代码：

#include <cstdio>
#include <queue>
using std::queue;

const int maxn=3e5+5;
struct node
{
    int t,s;
};
queue<node> q;
int n,w[maxn];

int main()
{
    scanf("%d",&n);
    int t,k,x,ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&t,&k);
        while(!q.empty())//先将24小时以前的人全部弹掉
        {
            if(q.front().t<=t-86400)//注意小于等于
            {
                if(!--w[q.front().s])//在这里，如果该国籍的人数-1之后变为0，那么总国籍数--
                    ans--;
                q.pop();
            }
            else
                break;
        }
        while(k--)
        {
            scanf("%d",&x);
            q.push((node){t,x});
            if(!(w[x]++))//如果该国籍原先没人，那么ans++。
                ans++;
        }
        printf("%d\n",ans);//每一艘船统计一次ans
    }
    return 0;
}