6.海港

阅读数: 次 2020-10-14

字数：707字 | 预计阅读时长：3分钟

前言

欢迎大家参与投稿，一经采用，稿酬从优😁
投稿方式:您可以通过我们的联系方式将内容打包发给我们进行审核（内容包括.md文件，昵称，有效联系方式，
题目标签，题目来源）。
联系方式见关于页

作者：Maksim

题目链接：洛谷

这道题文字很多，光是看完并理解，我都花了几分钟。不过这道题并没有用到十分高深的算法，对于我这样的蒟蒻选手已经算是很友好了。

思路

STL大法好！！！
先声明几个变量

1	int t[maxn];

这里记录了船的时间信息

struct Ship
{
    int cnt;
    vector<int>passenger;
}ship[maxn]; // maxn = 100005

用结构体来储存每艘船成员的国籍，这里使用的是矢量而不是副本是因为不想一开始就有太大的空间消耗。cnt则是我们后来要输出的答案

1	queue<int>s;

用一个体积来储存船（这里就用船的编号i来代理了船所以类型是int）

1	unordered_map<int, int>passenger;

用一个哈希表来记录成员

1 2	passenger[x] = k 表示国籍为x的成员一共有k个

接下来说一下操作的思路

每输入一艘船时，就记录船的时间，把每个乘客的信息放进该船的vector中并载客[x] ++，同时将船上编号放入。

之后就是根据题意，开始判断一天之内了
方法：

while(得到队首元素即船的编号，判断是否超过了一天)
    否：退出循环
    是：
        遍历这艘船的vector内每个乘客 x
        passenger[x]--
        如果passenger[x]已经等于0，则删除这个键值对
跳出循环后
这艘船的cnt = passenger.size()

复杂度应该是线性的？？这我懒得推导。

发一下自己的垃圾代码

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
#define maxn 100005
using namespace std;
typedef long long ll;
const int AdayTime = 86400;

struct Ship
{
    int cnt;
    vector<int>passenger;
}ship[maxn];

queue<int>s;
int t[maxn];
unordered_map<int, int>passenger;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int k;
        scanf("%d%d", &t[i], &k);
        s.push(i);

        while (k--)
        {
            int x;
            scanf("%d", &x);
            ship[i].passenger.push_back(x);
            if (!passenger[x])
            {
                passenger[x] = 1;
            }
            else
            {
                passenger[x]++;
            }
        }

        while (t[i] - t[s.front()] >= AdayTime)
        {
            for (auto u : ship[s.front()].passenger) {
                passenger[u]--;
                if (passenger[u] == 0)
                {
                    passenger.erase(u);
                }
            }
            s.pop();
        }

        ship[i].cnt = passenger.size();

    }
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", ship[i].cnt);
    }
    return 0;
}

综上，这题没有什么深奥的算法，所有的都可以靠STL模板实现，所以大家要对STL模板十分熟练哟。

第一次正式发题解〜

本文作者： 益题 Yitee
发布时间： 2020-10-14
最后更新： 2021-08-19
本文标题： 6.海港
本文链接： https://yitee.top/posts/57122.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！