needed help on spoj problem KOPC12A - K12 - Building Construction

general
,
1

link text

 #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
ll check(vector<int> &v ,vector<int> &c, int h){
    ll sum = 0;
    for(int i = 0 ; i < v.size() ; i++){
        ll diff = abs(v[i] - h);
        sum += diff*c[i];
    }
    return sum;
}
ll b_search(vector<int> &v , vector<int>&c){
    ll low = 0 , mid , high = INT_MAX;
    ll p , n , m , ans = LLONG_MAX;
    while(low<high){
        mid = (low+high)>>1;
        mid > 0 ? p = check(v , c , mid-1): INT_MAX;
        m = check(v , c , mid);
        n = check(v , c , mid+1);
        if(ans == m)
            break;
        ans = min(ans , m);
        if(p <= m)
            high = mid;
        else if(n <= m)
            low = mid+1;
    }
    return ans;
}
int main(){
    
    int t;
    scanf("%d" , &t);
    while(t--){
        int n , temp;
        scanf("%d",&n);
        vector<int> v(n) , c(n);
        for(int i = 0 ; i < n ; i++){
            scanf("%d",&temp);
            v[i] = temp;
        }
        for(int i = 0 ; i < n ; i++){
            scanf("%d",&temp);
            c[i] = temp;
        }
        printf("%lld\n", b_search(v , c));
    }
    
    return 0;
}

for the test case

1
5
2 4 6 8 9
10 30 40 50 80

my answer is coming 390.
but by manual calculation it should be 340 for h=8.

2

can you please post your code in ideone and share the link? It is unreadable.

3

please see the code on below link

4

The high in the binary search search must be set to mid+1 when p<=m and low must be set to mid when n<=m.Here is your AC solution.Here

5

thanks for help

6

Fixed formatting.

7

My code also works.

    import java.util.*;
    public class KOPC12A {
public static void main(String[] args) {
	Scanner s=new Scanner(System.in);
	int t=s.nextInt();
	while(t--!=0)
	{
		int n=s.nextInt();
		int heights[]=new int[n];
		int costs[]=new int[n];
		int max=Integer.MIN_VALUE;
		for(int i=0;i<n;i++)
		{
			heights[i]=s.nextInt();
			max=Math.max(max, heights[i]);
		}
		for(int i=0;i<n;i++)
		{
			costs[i]=s.nextInt();
		}
		
		int l=0,h=max;
		long ans=Long.MAX_VALUE;
		while(l<=h)
		{
			int mid=(l+h)/2;
			long amid1=cost(heights,costs,mid);
			long amid2=Long.MAX_VALUE;
			if(mid+1<=max)
			amid2=cost(heights,costs,mid+1);
			
			ans=Math.min(ans, amid1);
			if(amid2<amid1)
			{
				l=mid+1;
			}
			else
			{	
				h=mid-1;
			}
			
		}
		System.out.println(ans);
	}

}

public static long cost(int[] heights,int[] costs, int height)
{
	long sum=0;
	for(int i=0;i<heights.length;i++)
	{
		sum+=Math.abs(heights[i]-height)*costs[i];
	}
	return sum;
}

}