列表

详情


NC231897. 简单的数据结构问题

描述

bs是一位火车站的工作人员。某日,bs想记录下一列火车中他在意的某些车厢中的乘客信息。
假设这列火车的车厢是无穷无尽的,每一秒都会有一节车厢恰好经过车站窗口。

对于第 i 节车厢,bs记录了它恰好经过的时间(单位:秒),车厢上的乘客数量 ki,以及每名乘客的国籍

bs统计了 n 节车厢的信息,但由于数据量的庞大,他想请你帮忙计算一下他想要的答案。
对于每一节bs统计过的车厢,需要得到以这节车厢到达时间为止的一整天中,bs已经记录了多少个国家的乘客。


直白地说,对于每个车厢p,在每个符合的时间段中,共有多少不同的国籍信息,表示这节车厢到站的时间。

输入描述

第一行输入一个正整数,表示bs统计了 节 车厢的信息。
接下来 n 行,每行描述一节车厢的信息:前两个整数 ti 和 ki 分别表示这节车厢到达站点的时间和其中乘客的数量,接下来 ki 个整数 表示车厢上乘客的国籍。
保证输入的 ti 是递增的,单位是秒;表示从bs一开始计时,这节车厢在第 ti 秒到达车站。

输出描述

输出 n 行,第 i 行输出一个整数表示第 i 节车厢到达后的统计信息。

示例1

输入:

1
10 10 6 2 7 2 1 5 6 1 6 10

输出:

6

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 780K, 提交时间: 2021-12-18 23:10:36

#include<iostream>
using namespace std;
int s,i,n,t,k,r,w[100001],x[300002],y[300002];

int main(){
    cin>>n;
    while(n--){
        cin>>t>>k;
        while(k--){
            y[++r]=t;cin>>x[r];
            if(!w[x[r]])s++;
            w[x[r]]++;
        }
        while(t-y[i]>=86400)
            if(!--w[x[i++]])s--;
        cout<<s<<endl;
    }
}

上一题