Gasoline editorial - Nov Lunchtime 2020

editorial
1

Div1: “CodeChef: Practical coding for everyone”
Div2: “CodeChef: Practical coding for everyone”

Approach : -

  1. Make pair for { cost , fuel } for each {i}.

  2. Sort the pairs according to cost in ascending order. Why? as we are given the cost per L , so we take first that value whose cost is less.

  3. we have to travel the exact N distance take this in rem = N (below code)

  4. Now iterate overall values there may be two possibilities -
    a) the remaining distance is greater than or equal to the max capacity of the tank
    => in this case we simply fill the tank with full capacity , [now we can travel more distance (which is equal to fuel added) ] , and add the cost ie,[ (cost per L )* (max fuel capacity) ] , and set rem = rem-(fuel added)

    b) the remaining distance is less to the max capacity of the tank then we fill the tank only remaining value . Why ? suppose car has 10L fuel capacity and we required only 2 litre then why we need to fill with 10L , fill only 3L

int main(){
fastio
lli t=1;
cin>>t;
while(t--) {
    lli n;
    cin>>n;
    lli f[n] , c[n];
    scanarr(f,n);
    scanarr(c,n);
    vector<pair<lli,lli>> vp;
    loop(i,n)
    {
        vp.pb({c[i],f[i]});
    }
    sort(all(vp));
    lli rem=n;
    lli ans=0;
    lli i=0;
    while(i<n)
    {
        lli fuel = vp[i].S; //max fuel we can fill up for cuureent car
        lli cst = vp[i].F;  // per L fuel cost
        if(fuel) // fuel must be there
        {
            if(fuel<=rem) // if fuel is less than remaining distance then fill the current car completely
            {
                rem-=fuel;
                ans += (fuel*cst);
            }
            else
            {
                ans += (rem*cst); // if fuel is more then remaining distance the fill only required petrol
                // suppose car has 10L fuel capacity  and we required only 2 litre
                // then why we need to fill with 10L , fill only 3L
                rem=0;
                break;
            }
        }
        i++;
        if(rem==0) 
            break;
    }
    
    print(ans);
  }
return 0;
}
7 Likes