昨晚心动网路第二题,求大佬指教一下
昨晚第二题卡了我好久,后来请教大佬,说是用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话说,我应该没理解错题吧。。。