In this HackerEarth Promotion problem solution, Ramesh is a hard-working employee.Seeing his dedication towards his work his boss decided to promote him. Ramesh was overjoyed on getting to know this.But soon he realized he needed to shift to another Town X. Ramesh needed to transport his n boxes to Town X for which he contacted the company “Packers and Movers”.This company sent him m trucks.Each truck took 1 hour to go from his house to Town X and another 1 hour to return.But each truck could carry only 1 box at a time and also each truck has a limit for the maximum weight of the box it can carry.A truck can be used multiple times. Since Ramesh is busy he gives you the job for finding the minimum time in which he can transfer all his n boxes to Town X.
HackerEarth Promotion problem solution.
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define NIL 0
#define INF (1<<28)
#define MAXN 200001
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 5000000007
#define total 500005
#define M 1000000007
typedef long long int int64;
int box[100005];
int truck[100005];
int n,m;
bool chck(int tim){
int c=0,b=0;
while(c<m){
for(int j=0;j<tim&&b<n&&truck[c]>=box[b];j=j+2)
b++;
c++;
}
if(b==n)
return true;
return false;
}
int main(){
int i;
cin>>n>>m;
for(i=0;i<n;i++)
cin>>box[i];
for(i=0;i<m;i++)
cin>>truck[i];
sort(box,box+n);
sort(truck,truck+m);
int lo=0,high=2*n,ans;
while(lo<=high){
int mid=(lo+high)/2;
if(chck(mid)){
ans=mid;
high=mid-1;
}
else
lo=mid+1;
}
cout<<ans;
return 0;
}
Second solution
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define CLR(a) a.clear()
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define FORi(i,a,b) for(LET(i,a) ; i<b; i++)
#define repi(i,n) FORi(i,(__typeof(n))0,n)
#define FOR(i,a,b) for(i=a ; i<b; i++)
#define rep(i,n) FOR(i,0,n)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define piw(n) printf("%d ",n)
#define pin(n) printf("%dn",n)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;
LL power(LL a, LL p, LL mod)
{LL ret = 1;while(p){if(p&1)ret = (ret*a)%mod;a=(a*a)%mod;p/=2;}return ret;}
int T[10000];
int A[10000];
int n,m;
bool f(int c)
{
if(m*c<n)return false;
int t = m-1;
int w = n-1;
while(w>=0)
{
if(T[t]<A[w])return false;
t--; w-=c;
}
return true;
}
int main()
{
cin>>n>>m;
repi(i,n)cin>>A[i]; sort(A,A+n);
repi(i,m)cin>>T[i]; sort(T,T+m);
if(A[n-1]>T[m-1]){cout<<"-1"; return 0;}
int l=0; int h=n;
int m;
while(h-l>1)
{
m = (l+h)/2;
if(f(m))h=m; else l=m+1;
}
while(f(l)==false)l++;
cout<<2*l-1;
return 0;
}