UVa - 11389 Solution ( The Bus Driver Problem Solution )

=>Try Yourself First. For help Scroll Down .

Target : If you search the Solution / Hints for this Problem You may find different Site Which provide you Soution / Hints. I didn't post this topic to Provide you the Solution . I would like to Provide you the Idea / Thought that will help you to Solve this Problem without Seeing Code. At different Hint Providing site like : Outsbook / Algorithmist / Worlds Of Seven / Methodes to Solve you will find How to solve it but You may not have a better view why they Give you such type of Hint to Solve this problem. Those whom are interested to Understand read the whole Post Otherwise you  may go to Code ( which is at Down ) / Read the clearance Directly . 

Thank You.

Clearance : Here you need to find the Minimum Overtime that you have to pay . How to find this ? After taking the input,

1. At First Sort the Morning Rout Length Array &  Evening Rout Length Array in Ascending Order . 
2. Then Initiate a loop from i to n and Check whether Sum of i'th Element of First Array & (n-i)'th Elemnent of the Second Array ( M[i] + E[n-i] ) is Greater than The Fixed Rout Length ( ' d ' according to the Problem ) is Greater than or not.

If it is then Increase the Overtime for Sum( M[i] + E[i] ) - d.

And then multiply Overtime with Rate/Hour ( ' r ' according to the problem ) .

 /* Although I have solved by Sorting in Ascending Order of First Array & Sorting in Descending Order of the Second Array.*/

=>   This part is only for those who Doesn't want only Hint / Solution 

This part is after Sorting point. Why you should do this ? Let's Assume the Problem is only for N = 2.
So we have ->  x1, y1, x2, y2 . ( x is Morning , y is evening )
Here we have 3 Condition to Follow :

a.	two morning Routes with x1 < x2,
b.	two evening Routs with y1 < y2, and
c.	any work beyond H hours is overtime.

Then , We wil find all Combination of Rout Length. 
That is :  x1 + y1, x1 + y2, x2 + y1, x2 + y2. We will try to find all the Combination's Result and Compare with ' d '. This Can be shown as a Matrix below :

	x1	x2
y1	max{x1 + y1 – d, 0}	max{x2 + y1 – d, 0}
y2	max{x1 + y2 – d, 0}	max{x2 + y2 – d, 0}

I wrote the max function ito the Matrix is to Check the Maximum Overtime Hours of each Cell. Now from conditions (a) and (b) we can say that :

(x1 + y1)< [ (x1 + y2) / (x2 + y1) ] < (x2 +y2)

Thus, if the entry in the last row and last column is 0 then all entries of the matrix are zero. Now , If Any Cell is not 0 then  the total amount of overtime hours would be x₁ + x₂ + y₁ + y₂ – 2d whichever schedule is used of the Matrix . Because you should do it for all N ( x1, y1, x2, y2) items . In that case lets compare the The Cell No : 1 - 4 & 2 - 3.

(x₁ + y₂ – d) + (x₂ + y₁ – d) = (x₁ + y₁ – d) + (x₂ + y₂ – d)

As you can see, If we Move (x₁ + y₁ – d)  to the Left then You will get an optimized result as the Moved terms is Smaller than other cells .And that must be less than  (x₂ + y₂ – d) or Equal to 0. As You should optimize the Overtime . Or, if you Move  (x₂ + y₂ – d) Than you may get a Negative result or Zero result which is not our opted Output .

Our goal is to assign the evening routes to minimize overtime. Start by pairing each X with a Y by any method you wish. Find an adjacent pair whose afternoon routes are “out of order;” that is, Xs is paired with Yi, and Xt paired with Yj, but s < t and i < j. This pair of Drivers meets the conditions for above observation so we can swap their evening routes without increasing the overtime. By the first observation this process eventually terminates with the evening routes in the suggested order with the assignments x₁+y2, x₂+y1.

## Description Courtesy : Click Here For More Details.
## You Can Also Find Another Discussion  Here.


Thanks For Reading . Hope You Got It . And the post understable for which I wrote. If you have any Query then Leave a Comment.


Code :

 #include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, d, r;
    vector<int>morning;
    vector<int>evening;
    while(scanf("%d %d %d", &n, &d, &r)==3 && n && d && r)
    {
        int x;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&x);
            morning.push_back(x);
        }
        sort(morning.begin(),morning.end());
        for(int i=0; i<n; i++)
        {
             scanf("%d",&x);
             evening.push_back(x);
        }
        sort(evening.begin(),evening.end(),greater <int>()); //greater <int>() is for Descending Order Sorting .
        int overtime = 0;
        for(int i=0; i<n; i++)
        {
            int h = morning[i] + evening[i];
            if(h>d)
                overtime = overtime + (h-d);
        }
       cout<<overtime*r<<endl;
       morning.clear();
       evening.clear();
    }
    return 0;
}

=>Question or Need Help ?? Leave a Comment .