Header Ad

HackerEarth Architect's Dilemma..! problem solution

In this HackerEarth Architect's Dilemma..! problem solution An Architect has been assigned a project and some number of workers work for him. Each of the workers is assigned a fixed amount of work. Suddenly, he has been appointed to build a new elegant office by the mayor. He won't disappoint the mayor and finish the task as quickly as possible.

Now, the architect has some amount of extra work to build the new office. He wants to assign this extra work to workers in such a way that there is a maximum number of workers with the same amount of total work. It might not be possible to give an equal amount of work to each worker. He wants to find a maximum number of workers possible with the same amount of total work. It is not necessary that the architect assigns all of his extra work.


HackerEarth Architect's Dilemma..! problem solution


HackerEarth Architect's Dilemma..! problem solution.

import java.util.*;
import java.io.*;

public class Problem {

public static void main(String[] args) throws IOException
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int w=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
Arrays.sort(a);
int max=1;
int sum=0,j=n-1;

for(int i=n-1;i>0;i--)
{

while(j>=0)
{
sum+=a[i]-a[j];
if(sum>w)
{
int temp=i-j;
if(temp>max)
max=temp;
sum-=a[i]-a[j];
sum-=(temp-1)*(a[i]-a[i-1]);
break;
}
j--;

}
if(j==-1 && sum<=w)
{
max=Math.max(max,i+1);
}
}
System.out.println(max);


}
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,w,a[100005],pre[100005],maxx[100005];
bool f(int x)
{
for(int i=0,j=x;j<=n;j++,i++)
{
if(x*maxx[j]-(pre[j]-pre[i])<=w)return 1;
}
return 0;
}
int main()
{
cin>>n;
cin>>w;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
//cout<<a[i]<<" ";
pre[i]=pre[i-1]+a[i];
maxx[i]=max(maxx[i-1],a[i]);
}
int l=1,r=n,ans;
while(l<=r)
{
int mid=(l+r)/2;
if(f(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<"\n";
return 0;
}

Post a Comment

0 Comments