牛客小白月赛22-货物种类

题目链接: https://ac.nowcoder.com/acm/contest/4462/H

在这里插入图片描述

思路

作为无脑型选手,上来看到这种区间题,不考虑复杂度(因为不会算QAQ),直接上来搓一发线段树,那结果超时是必然的!!!(后面才想到有个差分序列….. 所以STL套一套 + 差分序列,求前缀和,就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, unordered_map<int, int> > mp;
void solve(unordered_map<int, int> &tmpa, unordered_map<int, int> &tmpb) {
for(auto i : tmpb) {
tmpa[i.first] += i.second;
if(tmpa[i.first] == 0){
tmpa.erase(i.first);
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
mp.clear();
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
if(a > b) swap(a, b);
mp[a][c]++;
mp[b + 1][c]--;
}
int ans = -1, maxn = 0;
unordered_map<int, int> tmp;
tmp.clear();
int sum = 0;
for(int i = 1; i <= n; i++){
solve(tmp, mp[i]);
int k = tmp.size();
if(k > maxn) {
maxn = k;
ans = i;
}
}
cout << ans << endl;
return 0;
}

本文标题:牛客小白月赛22-货物种类

文章作者:HKer_YM

发布时间:2020年02月23日 - 13:19:02

最后更新:2020年03月01日 - 18:13:32

原始链接:https://blog.dreams-wj.top/2020/02/23/%E7%89%9B%E5%AE%A2%E5%B0%8F%E7%99%BD%E6%9C%88%E8%B5%9B22-%E8%B4%A7%E7%89%A9%E7%A7%8D%E7%B1%BB/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。