-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
853.cpp
64 lines (60 loc) · 2.03 KB
/
853.cpp
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
__________________________________________________________________________________________________
typedef pair<int, int> pint;
typedef vector<pint> vpint;
class pcomp {
public:
bool operator()(const pint& p1, const pint&p2){
return p1.first<p2.first;
}
};
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
// positions aren't sorted!
vpint plist;
for(int pos=0; pos<position.size(); pos++){
plist.push_back(pint(position.at(pos), speed.at(pos)));
}
sort(plist.begin(), plist.end(), pcomp());
int tot_fleets = 0;
double next_fleet_arrival = -1.0, curr_arrival_time=-1.0;
for(int pos=plist.size()-1; pos>=0; pos--){
curr_arrival_time = (target-plist.at(pos).first)*1.0/plist.at(pos).second;
if(curr_arrival_time>next_fleet_arrival){
tot_fleets++;
next_fleet_arrival = curr_arrival_time;
}
}
return tot_fleets;
}
};
static int optimize = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return 0;
}();
__________________________________________________________________________________________________
sample 10732 kb submission
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
if(position.size()<=1) return position.size();
vector<int> ind(position.size());
int i = 0;
iota(ind.begin(),ind.end(),i++);
sort(ind.begin(),ind.end(),[&](int a,int b){return position[a]>position[b];});
int last = 0;
int fleets = 1;
double tar = target;
for(int i = 0; i<ind.size(); i++)
{
if( (tar - position[ind[last]])*speed[ind[i]]<(tar - position[ind[i]])*speed[ind[last]])
{
fleets++; last = i;
}
}
return fleets;
}
};
__________________________________________________________________________________________________