货物种类

[编程题]货物种类

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某电商平台有n个仓库，编号从1到n。

当购进某种货物的时候，商家会把货物分散的放在编号相邻的几个仓库中。

我们暂时不考虑售出，你是否能知道，当所有货物购买完毕，存放货物种类最多的仓库编号为多少？

输入描述:

在第一行中给出两个正整数，分别代表仓库的数目和进货的次数。
接下来 m 行，每行三个正整数。编号在l和r之间的仓库收进编号为d的货物。
（包括l和r）

输出描述:

在一行中输出存放货物种类最多的仓库编号，若满足条件的仓库不止一个，则输出编号最小的那个。

示例1

输入

输出

算法知识视频讲解

RandolphJ

发表于 2020-03-02 07:41:12

有n个仓库，m次操作，每次在l和r之间的仓库收进编号为d的货物。最后求存放货物种类最多的仓库编号。在区间内实现加减，我们可以使用差分数组。还要注意的一点：不是存放货物数目最多，而是存放货物种类最多，为了防止重叠区间重复计算答案，我们可以先将区间读下来，排个序（先按编号从小到大，编号相同按起始位置从展开全文

炒鸡炒鸡炒鸡

发表于 2021-10-05 20:54:58

题解：该题使用贪心的解题思路吧货物序号从小到大排序通过a,b数组来计算结果 #include<bits/stdc++.h> using namespace std; const int N=100010; struct node { int l,r,date; bool 展开全文

Rain_Fly

发表于 2024-03-13 21:46:30

最近补题，写到了这个很有意思的差分，乍一看就是一个差分，仔细一看，要找的是货物种类最多的仓库编号，注意是种类！所以，对每一次放货物，我们不能直接对差分数组操作，我们需要先把每一次操作存储起来，然后排序，进行相同种类的货物区间合并，对于排序规则，我们以种类为第一要素比较，然后比较左端点，左端点展开全文

Z_L_G

发表于 2025-03-10 13:41:42

题意 n个点，m次输入，每次输入左界，右界，存储的货物编号求存储的货物种类最多的点思路因为一个点可能重复读入同一个货物，所以使用map并做前缀和开一个map统计每个点存入的货物和次数，全部读入完后，开第二个前缀和map 遍历第一个map中的每一个点，对每一个点，将其中的货物存入前缀和m 展开全文

dass90

发表于 2022-10-03 18:07:52

thinking process use struct to store order info. struct ty{ int l, r, c; }a[100010]; compare operator defination: a.c == b.c ? a.l < b.l : a.c 展开全文

装糊涂高手_

发表于 2021-12-25 11:16:41

枚举，差分，离散化题中给的数据范围太大，开个大数组暴力枚举不现实，考虑离散化处理，同时维护一个差分数组存储每个仓库的货物种类。 1、利用结构体把每次进货的信息存储好； 2、自定义升序排序规则，货物编号优先级第一，区间起点优先级第二； 3、定义两个临时变量存储临时起点和临时终点； 4、若第j个结构体展开全文