this is problem Problem - A - Codeforces
this is my code QpwULo - Online C++0x Compiler & Debugging Tool - Ideone.com
it give me wrong answer
@tarek7889
try the case:
7 2
27 27 27 27 27 27 27
25 29
the answer should be 13 as only one car is capable of moving the weights but your code gives it as 7.
1 Like
if have you have any approach explain it.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> weight, cars;
for(int i = 0; i < n; i++){
int x;
cin >> x;
weight.pb(x);
}
for(int i = 0; i < m; i++){
int x;
cin >> x;
cars.pb(x);
}
sort(weight.begin(), weight.end());
sort(cars.begin(), cars.end());
int trip = 0;
int k = 0;
int sz = n;
while(sz > 0){
for(int i = k; i < m; i++){
auto it = upper_bound(weight.begin(), weight.end(), cars[i]);
if(it == weight.begin()){
k++;
}
else{
it -= 1;
weight.erase(it);
sz--;
}
}
trip++;
}
cout << 2*trip - 1 << "\n";
return 0;
}
The basic idea is to find cars “eligible” to make a certain trip.
A car is eligible to make a trip if there exists at least one weight which is less than or equal to it.
To make the process efficient, we choose the first weight just smaller than the maximum weight of the car.