拼多多2018校招编程题链接-牛客网
1. 列表补全
题目描述
在商城的某个位置有一个商品列表，该列表是由L1、L2两个子列表拼接而成。当用户浏览并翻页时，需要从列表L1、L2中获取商品进行展示。展示规则如下：
1. 用户可以进行多次翻页，用offset表示用户在之前页面已经浏览的商品数量，比如offset为4，表示用户已经看了4个商品
2. n表示当前页面需要展示的商品数量
3. 展示商品时首先使用列表L1，如果列表L1长度不够，再从列表L2中选取商品
4. 从列表L2中补全商品时，也可能存在数量不足的情况
请根据上述规则，计算列表L1和L2中哪些商品在当前页面被展示了
输入描述
每个测试输入包含1个测试用例，包含四个整数，分别表示偏移量offset、元素数量n，列表L1的长度l1，列表L2的长度l2。
输出描述
在一行内输出四个整数分别表示L1和L2的区间start1，end1，start2，end2，每个数字之间有一个空格。
注意，区间段使用半开半闭区间表示，即包含起点，不包含终点。如果某个列表的区间为空，使用[0, 0)表示，如果某个列表被跳过，使用[len, len)表示，len表示列表的长度。
样例
in
2 4 4 4
1 2 4 4
4 1 3 3out
2 4 0 2
1 3 0 0
3 3 1 2
思路解析
模拟题，考虑几种情况
代码一
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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// 列表补全
int main() {
int offset, n, l1, l2;
while (cin >> offset >> n >> l1 >> l2) {
int start1, end1, start2, end2;
if (offset < l1) {
start1 = offset;
end1 = min(l1, offset + n);
if (offset + n <= l1) {
start2 = end2 = 0;
} else {
start2 = 0;
end2 = min(l2, offset + n - l1);
}
} else if (offset < l1 + l2){
start1 = end1 = l1;
offset -= l1;
start2 = offset;
end2 = min(l2, offset + n);
} else {
start1 = end1 = l1;
start2 = end2 = l2;
}
cout << start1 << " " << end1 << " " << start2 << " " << end2 << endl;
}
return 0;
}代码二
1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
int main() {
int offset, n, l1, l2;
while (~scanf("%d%d%d%d", &offset, &n, &l1, &l2))
printf("%d %d %d %dn", min(l1, offset), min(l1, offset+n), min(max(offset-l1, 0), l2), min(max(offset+n-l1, 0), l2));
return 0;
}2. Anniversary
题目描述
拼多多王国的城市和道路的拓扑结构比较特别，是一个树状结构：
1. 每个城市是树的一个节点；
2. 城市之间的道路是树的一条边；
3. 树的根节点是首都。
拼多多周年庆马上就要到了，这是拼多多王国的一个大日子。为了活跃气氛，国王想在道路上布置花灯。花灯可是很贵的东西，尽管国王想要在所有道路上都布置花灯，但是如果要花太多钱的话，是过不了财政大臣那一关的。国王把这个计划告诉财政大臣，最后他们商讨出来这么一个方案：
1. 一条道路要么不布置花灯，要么整条布置花灯，不能选择其中的某一段布置；
2. 除非没有道路通向首都，否则至少为一条通向首都的道路布置花灯；
3. 所有布置花灯的道路构成的子图是连通的，这保证国王从首都出发，能通过只走布置了花灯的道路，把所有的花灯游览完；
4. 如果某个城市（包括首都）有大于等于2条道路通向子城市，为了防止铺张浪费，最多只能选择其中的两条路布置花灯；
5. 布置花灯的道路的总长度设定一个上限。
在上述方案下，国王想要使得布置花灯的道路长度越长越好，你帮国王想想办法。
输入描述
每个测试输入包含1个测试用例。
输入的第一行是一个正整数m，0< m<=9900，表示布置花灯的道路的总长度的上限。
输入的第二行是一个正整数n，n<=100，表示城市的个数。
紧接着是n-1行输入，每行三个正整数u、v、d，表示下标为u的城市有一条长度为d的道路通向它的一个子城市v，其中0 <= u< n，0<= v< n，0< d<= 100。
输出描述
输出一个正整数，表示能布置花灯的道路长度的最大值
样例
in
5
5
0 1 1
0 2 2
0 3 3
0 4 4out
5
思路解析
待解析
代码
待完善
3. 数三角形
题目描述
给出平面上的n个点，现在需要你求出，在这n个点里选3个点能构成一个三角形的方案有几种。
输入描述
第一行包含一个正整数n，表示平面上有n个点（n <= 100)
第2行到第n + 1行，每行有两个整数，表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100，且保证所有坐标不同）
输出描述
输出一个数，表示能构成三角形的方案数。
样例
in
4
0 0
0 1
1 0
1 1out
4
思路解析
数据量小，暴力，三层循环
代码
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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct Point {
int x;
int y;
Point(int a, int b): x(a), y(b) {}
};
// 数三角形
int main() {
int n; cin >> n;
vector<Point> points;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
points.push_back(Point(x, y));
}
int ans = 0;
for (int i = 0; i < n - 2; ++i) {
auto a = points[i];
for (int j = i+1; j < n - 1; ++j) {
auto b = points[j];
for (int k = j+1; k < n; ++k) {
auto c = points[k];
if ((a.x-b.x)*(a.y-c.y) != (a.x-c.x)*(a.y-b.y)) {
++ans;
}
}
}
}
cout << ans <<endl;
return 0;
}4. 最大乘积
题目描述
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
输入描述
第一行是数组大小n，第二行是无序整数数组A[n]
输出描述
满足条件的最大乘积
样例
in
4
3 4 1 2out
24
思路解析
保存5个数，min1 < min2 < max1 < max2 < max3;分正数，0，负数讨论
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void update_max(int &a, int &max1, int &max2, int &max3) {
if (max3 < a) {
max1 = max2; max2 = max3; max3 = a;
} else if (max2 < a) {
max1 = max2; max2 = a;
} else if (max1 < a) {
max1 = a;
}
}
void update_min(int &a, int &min1, int &min2) {
if (a < min1) {
min2 = min1; min1 = a;
} else if (a < min2) {
min2 = a;
}
}
// 最大乘积
int main() {
int n; cin >>n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (auto &a : nums) {
update_max(a, max1, max2, max3);
update_min(a, min1, min2);
}
LL ans = 1;
if (max1 > 0) {
if (min2 < 0) {
ans = ans*max3 * max(ans*max1*max2, ans*min1*min2);
} else {
ans = ans*max1*max2*max3;
}
} else if (max1 == 0) {
if (max2 == 0) {
if (max3 > 0) {
ans = ans*min1*min2*max3;
} else {
ans = 0;
}
} else {
ans = ans*min1*min2*max3;
}
} else {
if (max3 > 0) {
ans = ans*min1*min2*max3;
} else {
ans = ans*max1*max2*max3;
}
}
cout << ans << endl;
return 0;
}
5. 小熊吃糖
题目描述
有n只小熊，他们有着各不相同的战斗力。每次他们吃糖时，会按照战斗力来排，战斗力高的小熊拥有优先选择权。前面的小熊吃饱了，后面的小熊才能吃。每只小熊有一个饥饿值，每次进食的时候，小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃，可能吃完没饱会重复上述过程，但不会选择吃撑。
现在给出n只小熊的战斗力和饥饿值，并且给出m颗糖能填饱的饥饿值。
求所有小熊进食完之后，每只小熊剩余的饥饿值。
输入描述
第一行两个正整数n和m，分别表示小熊数量和糖的数量。（n <= 10, m <= 100）
第二行m个正整数，每个表示着颗糖能填充的饥饿值。
接下来的n行，每行2个正整数，分别代表每只小熊的战斗力和当前饥饿值。
题目中所有输入的数值小于等于100。
输出描述
输出n行，每行一个整数，代表每只小熊剩余的饥饿值。
样例
in
2 5
5 6 10 20 30
4 34
3 35out
4
0
样例说明
第一只小熊吃了第5颗糖
第二只小熊吃了第4颗糖
第二只小熊吃了第3颗糖
第二只小熊吃了第1颗糖
思路解析
对小熊的战斗值从大到小排序，根据从小到大的排序的糖果提供的饥饿值选择，吃完删除
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct Node {
int idx;
int fight;
int hungry;
Node()=default;
Node(int i, int f, int h): idx(i), fight(f), hungry(h) {}
bool operator< (const Node &a) const {
return fight > a.fight;
}
};
// 小熊吃糖
int main() {
int n, m; cin >> n >> m;
vector<int> nums(m);
for (int i = 0; i < m; ++i) {
cin >> nums[i];
}
// sort(nums.begin(), nums.end());
vector<Node> bears;
for (int i = 0; i < n; ++i) {
int f, h; cin >> f >> h;
bears.push_back(Node(i, f, h));
}
sort(bears.begin(), bears.end());
vector<int> ans(n);
for (auto &bear : bears) {
while (bear.hungry > 0) {
sort(nums.begin(), nums.end());
auto iter = upper_bound(nums.begin(), nums.end(), bear.hungry);
if (iter != nums.begin()) {
bear.hungry -= *(iter - 1);
// *(iter - 1) = 0;
swap(*(iter - 1), nums.back());
nums.pop_back();
} else {
ans[bear.idx] = bear.hungry;
break;
}
}
}
for (auto &a : ans) {
cout << a << endl;
}
return 0;
}
最后
以上就是霸气羽毛最近收集整理的关于拼多多2018校招编程题部分题解的全部内容，更多相关拼多多2018校招编程题部分题解内容请搜索靠谱客的其他文章。
发表评论 取消回复