includevector

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;}