腾讯WXG一面凉经

上来两道编程题，一道都没有搞出来
第一题不能用排序，复杂度太大两两配对

两两配对

小Q有M(M为偶数)名员工, 第i名员工完成工作的时候有一个拖延时间值t_i。
现在小Q手里有M/2份工作需要完成, 每一份工作都需要安排两名员工参与, 对于第i份工作所需完成的时间为两名员工的拖延时间值总和。
现在M/2份工作同时开始进行,小Q希望所有工作结束的时间尽量早, 请你帮小Q设计一个优秀的员工分配方案,使得用尽量少的时间完成所有工作,并输出工作所需的最短时间。

输入描述

第一行为一个正整数。
接下来有n行，每行两个正整数x和y，表示有x名员工的拖延时间值为。保证所有x的总和等于, 保证M为偶数。

输出描述

输出工作所需的最短时间。

示例1

输入

输出

说明
拖延值为8的和拖延值为2的组队，两名拖延值为5的组队，所以完成工作的时间为10，这是时间最短的方案。

最大最小之差

小Q的好朋友牛牛在纸上写了长度为n的正整数数列。
牛牛要求小Q每次从数列中选取两个数a,b，把这两个数从数列中移除出去，然后在数列中加入a * b + 1，直到只剩一个数为止。
小Q发现根据操作顺序的不同，最后得到的数的大小也不一样。
小Q现在想让你帮他计算，在所有情况中能获得的最大值减去能获得的最小值等于多少？

输入描述

第一行一个正整数n(1 <= n <= 50)，表示正整数序列的长度；
在接下来的n行中，每行输入一个正整数ai，即初始数列中的每一个数。保证所有数据计算结果均在64位有符号整数范围内。

输出描述

输出一个数，表示最大最小之差。

示例1

输入

输出

其他的就不说了，大概问了以下几个

线程和进程和协程
MySQL唯一索引和主键索引
MySQL的脏读和幻读
HTTPS和HTTP

我好弱鸡啊

#腾讯##面经##秋招##Java工程师#

全部评论

推荐最新楼层

土肥圆哥哥

中国科学院大学 C++

大小差肯定只能是大小堆 #include<bits/stdc++.h> using namespace std; int main() { int N; cin >> N; priority_queue<int>bigheap; priority_queue<int, vector<int>, greater<int>> smallheap; for (int i = 0; i < N; i++) { int tem; cin >> tem; bigheap.push(tem); smallheap.push(tem); } while (bigheap.size() != 1) { int a = bigheap.top(); bigheap.pop(); int b = bigheap.top(); bigheap.pop(); bigheap.push(a * b + 1); } int min = bigheap.top(); while (smallheap.size() != 1) { int a = smallheap.top(); smallheap.pop(); int b = smallheap.top(); smallheap.pop(); smallheap.push(a * b + 1); } int max = smallheap.top(); cout << max - min<<endl; return 0; }

点赞回复分享

发布于 2019-08-28 16:38

土肥圆哥哥

中国科学院大学 C++

第一题用map存数据不知道有木有更好的做法 #include<bits/stdc++.h> using namespace std; int main() { int N; cin >> N; map<int, int>m; map<int, int>::iterator begin,end; for (int i = 0; i < N; i++) { int num; int time; cin >> num >> time; m.insert({ time,num }); } int res = 0; while (m.size() != 0) { begin = m.begin(); end = m.end(); end--; res = res > (begin->first + end->first) ? res : (begin->first + end->first); begin->second--; if (begin->second == 0) { m.erase(begin); } end->second--; if (end->second == 0) { m.erase(end); } } cout << res << endl; return 0; }

点赞回复分享

发布于 2019-08-28 16:36

悲伤与奶同大

华东师范大学 C++

第一题让最大的最小，所以用二分 bool judge(int val) { set<int> s = total_set; while(!s.empty()) { int val1 = *s.begin(); int val2 = val - val1; auto find = s.upper_bound(val2); if (*find + val1 > val) { return false; } else { s.erase(s.begin()); s.erase(find); } } return true; } bs() { l = 0; r = sum_of(arr); while (l < r) { int mid = (l + r) / 2; if (judge(mid)) { l = mid + 1; } else { r = mid; } } return l; }

点赞回复分享

发布于 2019-08-29 18:50

offer快来吧。！！

哈尔滨工程大学测试工程师

问项目了吗

点赞回复分享

发布于 2019-08-29 13:33

落水鱼

哈尔滨工程大学 Java

第一题贪心可以么? 排序之后最小的只能和最大的匹配.向中间靠拢. 总感觉哪里不对,但是好像想着没毛病啊.

点赞回复分享

发布于 2019-08-28 16:09