2022-04-10 22:52 东南大学 C++
关注
2022年4月10日拼多多笔试第四题
#拼多多# 有m辆车要通过摆渡船到对岸去，一次摆渡最多装n辆车，一次从一侧到对岸的时间为x,往返时间为2x,求最后一辆车到达对岸的最短时间.
思路：贪心算法，尽量摆渡船尽量载满再出发，因为如果有两辆车分两次摆渡，需要等待摆渡船返回的时间。只有在后续车辆距离第一辆上船车辆的时间大于2x时才不等后续车辆。
#include<iostream>
(5488)#include<string>
#include<vector>
(7278)#include<iomanip>
#include<algorithm>
(5863)#include<unordered_map>
using namespace std;
int main() {
int m, n, x;
cin >> m >> n >> x;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin>>a[i];
}
sort(a.begin(), a.end());
int t=0;
for(int i=0;i<m;++i){
int temp = i;
for (int j = 1; j + i < m&&j<n; ++j) {
if (a[i + j] - a[i] <= 2 * x) {
temp = i + j;
}
else {
break;
}
}
t =max(t,a[temp])+2*x;
i = temp;
}
t = t - x;
cout << t;
return 0;
}
#拼多多# 有m辆车要通过摆渡船到对岸去，一次摆渡最多装n辆车，一次从一侧到对岸的时间为x,往返时间为2x,求最后一辆车到达对岸的最短时间.
思路：贪心算法，尽量摆渡船尽量载满再出发，因为如果有两辆车分两次摆渡，需要等待摆渡船返回的时间。只有在后续车辆距离第一辆上船车辆的时间大于2x时才不等后续车辆。
#include<iostream>
(5488)#include<string>
#include<vector>
(7278)#include<iomanip>
#include<algorithm>
(5863)#include<unordered_map>
using namespace std;
int main() {
int m, n, x;
cin >> m >> n >> x;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin>>a[i];
}
sort(a.begin(), a.end());
int t=0;
for(int i=0;i<m;++i){
int temp = i;
for (int j = 1; j + i < m&&j<n; ++j) {
if (a[i + j] - a[i] <= 2 * x) {
temp = i + j;
}
else {
break;
}
}
t =max(t,a[temp])+2*x;
i = temp;
}
t = t - x;
cout << t;
return 0;
}
全部评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
小浪_Coding：工作只是谋生的手段 而不是相互比较和歧视
点赞 评论 收藏
分享