昨晚心动网路第二题,求大佬指教一下

昨晚第二题卡了我好久,后来请教大佬,说是用map记录,set辅助,很容易就出来了。。。(然鹅我是第一次听说map和set啊!)

然后某度了一下相关的算法,补齐了昨晚没写完的代码,发出来给大佬们检查一下,看看有没有其他的可以更优化的地方😶
#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	std::map<int,int> N;//<数, 出现次数>
	for (int i = 0; i<n; i++) {
		int l;
		cin >> l;
		vector<int> L(l+1);
		int sum = 0;
		for (int j = 0; j<l; j++) {
			cin >> L[j];
			sum += L[j];
		}
		L[l] = 0;//记得样例里边有一组没有删数就直接求和了,相当于多出来一个0
		set<int> s;//用set标记,同一组数里面有重复的就不计算第二次了
		for (int j = 0; j<=l; j++) {
			int temp = sum - L[j];
			if (s.find(temp) == s.end()) {
				s.insert(temp);
				if (N.find(temp) != N.end()) {
					N[temp] += 1;
				}
				else {
					N[temp] = 1;
				}
			}
		}
	}
	int ans = 0;
	//遍历所有求和结果,找出出现次数最多的那个
	std::map<int, int>::iterator iter;
	for ( iter = N.begin(); iter != N.end(); iter++) {
		if ((iter->second) > ans) {
			ans = iter->second;
		}
	}
	cout << ans;
	return 0;
}
测试样例:
5
4 2 3 4 1
3 1 6 2
5 4 5 7 3 2
3 3 6 3
4 10 1 6 5
输出:
3
话说,我应该没理解错题吧。。。

另外还想问一下,是不是在需要对数简单排序的时候,直接用set不用vector更好一些?

#C++工程师#
全部评论
set和map如果对排序没有要求就换成unordered_set/map
点赞 回复
分享
发布于 2020-02-29 17:01

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务