collect the balls between two Roads

collect the balls between two Roads

  February 27, 2019    

---

Problem :

There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain some balls. bucket place in non decreasing order
The geek can change the road only at the point of intersection(which means, buckets with the same number of balls on two roads). Now you need to help Geek to collect the maximum number of balls.


Input:

1
5 5   // n , m
1 4 5 6 8
2 3 4 6 90

Output :110

Explanation:
here we start with 2 and switch road from 4 then again switch to 6
So 2+3+4+5+6+90 =110

Approach:

here we can use merge concept of mergesort so try to iterate list until common point and assign max value .

Consider case when more than 1 bucket has same balls :)



Code:

  public static long fn(int a[],int b[],int n,int m)
  {
      long first=0,second=0,res=0;
      int i=0,j=0;
      while(i<n&& j<m)
      {
          if(a[i]<b[j]){
              first+=a[i++];
          }
          else if(a[i]>b[j])
          {
              second+=b[j++];
          }
          else
          {
              res+=Math.max(first,second)+a[i];
              first=0;
              second=0;
              int temp=a[i];
              ++i;
              temp=b[j];
              ++j;
              while(i<n && a[i]==temp)
              res+=a[i++];
              while(j<m && b[j]==temp)
              res+=b[j++];
          }
      }
      while(i<n)
      {
          first+=a[i++];
      }
      while(j<m)
      {
         second+=b[j++];
      }
      res+=Math.max(first,second);
      return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int m=ab.nextInt();
    int arr[]=new int[n];
    int arr2[]=new int[m];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    for(int i=0;i<m;++i)
    arr2[i]=ab.nextInt();
    System.out.println(fn(arr,arr2,n,m));
}

}