11389 - The Bus Driver Problem

[drik_wen]

Code: Select all

import java.util.Scanner;
public class bus_driver
{
   public static void main(String[] args)
   {
      Scanner read=new Scanner(System.in);
      int drivers=10;
      int exceeds=10;
      int pay=10;
      int overpay=0;
      int [] morning;
      int [] evening;
      int temp=1000000;
      int total=0;
      int count=-1;
      while(read.hasNext())
      {
         drivers=read.nextInt();
         exceeds=read.nextInt();
         pay=read.nextInt();
         if(drivers==0 && exceeds==0 && pay==0)
            break;
         morning=new int[drivers];
         evening=new int[drivers];
         for(int i=0;i<drivers;i++)
         {
            morning[i]=read.nextInt();
         }
         for(int j=0;j<drivers;j++)
         {
            evening[j]=read.nextInt();
         }
         for(int k=0;k<drivers;k++)
         {
               overpay=morning[k]+evening[k];         
            if(overpay>exceeds)
            {
               if(overpay<temp)
               {
                  temp=overpay;
               }
               total=(temp-exceeds)*pay;
               count=1;
            }
         }
         if(count==1)
            System.out.println(total);
         else
            System.out.println(0);
      }
   }

}


is there something wrong on my coding..?? I still can't get AC on this problem..
or may be I misunderstand what the problem want, but i didnt realize it..
can somebody help me please..
thank in advanced..

[nymo]

Your code is wrong. Think about a greedy approach using sorting.

[Nahiyan Kamal]

can anyone show me why sorting and adding like this gives the minimum result? can anyone show the proof?

[zobayer]

@NK, I am not sure if it's the right way to prove something, but these are the thoughts went through my mind when I solved this one.

Say for n = 2, we have a1, b1 and a2, b2. And without loss of generality, lets assume, a1 <= b1 and a2 <= b2, also, a1 + b2 <= a2 + b1 (as these assumption don't cause any difference).
Now, we could choose (a1, a2) and (b1, b2) or (a1, b2) and (a2, b1).
We have
a1 + a2 <= b1 + b2
Also,
a1 + b2 <= a2 + b1 <= b1 + b2
Similarly,
a1 + a2 <= a1 + b2 <= a2 + b1
Combining,
a1 + a2 <= a1 + b2 <= a2 + b1 <= b1 + b2

Now lets assume, d is the limit we don't want to cross.
So, we can have 3 situations here,
(1) d <= a1 + a2
(2) a1 + a2 <= d1 <= b1 + b2
(3) b1 + b2 <= d

And from previous setp
a1 + a2 <= a1 + b2 <= a2 + b1 <= b1 + b2
So, for all the abobe cases, [d ~ (a1, a2)] + [d ~ (b1, b2)] >= [d ~ (a1, b2)] + [d ~ (a2, b1)]
Because, both (a1, b2) and (a2, b1) lies somewhere between (a1, a2) and (b1, b2).

This can be extended to n > 2 situations in the same way. For this reason, the strategy of minimizing average sum yields the solution, and hence, greedy works here.

Hope it's understandable.

[plamplam]

Code: Select all

5 20 5
13 17 19 27 3
55 16 6 26 7
7 18 3
1 2 3 4 5 6 7
12 324 343 121 343 121 121
10 16 4
16 191 17 18 15 14 121 26 8 3
4 18 16 17 14 101 12 3 120 12
0 0 0


Code: Select all

445
3861
2344


[shuza]

my code is giving the same result but getting wa can anyone give critical input??????