In this HackerRank Drive problem solution, The bus is equipped with K units of Nitro (N2O). If going from station one to station two takes x seconds, then using t units of nitro can decrease the time taken to max(x-t, 0) seconds where max(a,b) denotes the greater of the two values between a & b. The Nitro can be used all at once or in multiples of 1 unit.
If the bus driver travels optimally, what is the minimum sum of traveling time for all commuters? The traveling time equals the time he/she arrived at the destination minus the time he/she arrived at the start station.
Problem solution in Java.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Drive {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
step[] steps = new step[scan.nextInt()];
passenger[] passengers = new passenger[scan.nextInt()];
int nitro = scan.nextInt();
loadStuff(scan,steps,passengers);
addPassengers(steps,passengers);
calcDepartures(steps);
Queue<run> runs = new PriorityQueue();
findruns(runs,steps);
saveNitro(steps,runs,nitro);
calcDepartures(steps);
System.out.println(passengerTime(steps,passengers));
}
static void saveNitro(step[] steps,Queue<run> runs,int nitroLimit){
long targetSaving = totalDistance(steps) - nitroLimit;
run r;
int s;
int x;
while(0<targetSaving){
r = runs.poll();
s = r.station;
x = steps[s].distance - steps[s].travelTime;
if(x>r.deadline){x=r.deadline;}
if(x>targetSaving){x=(int)targetSaving;}
steps[s].travelTime += x;
r.deadline -= x;
targetSaving -= x;
if ((0<s) && (0 < r.deadline)){
r.carrying += steps[s].dropped;
r.station--;
runs.add(r);
}
}
}
static long totalDistance(step[] steps){
long distance=0;
for(step s : steps){
distance += s.distance;
}
return distance;
}
static void printruns(Queue<run> runs){
for(run r : runs){
System.out.println("~~~~~~~~");
System.out.println("station : "+String.valueOf(r.station));
System.out.println("deadline : "+String.valueOf(r.deadline));
System.out.println("tocarry : "+String.valueOf(r.carrying));
}
}
static void findruns(Queue<run> runs,step[] steps){
steps[steps.length-1].departure = 2000000000;
for(int i=0;i<steps.length-1;i++){
if(steps[i].departure < steps[i+1].departure){
run r = new run();
r.station = i;
r.deadline = steps[i+1].departure - steps[i].departure;
r.carrying = steps[i+1].dropped;
runs.add(r);
}
}
}
static long passengerTime(step[] steps,passenger[] passengers){
long total = 0;
for(passenger p : passengers){
total += steps[p.dest-1].departure + steps[p.dest-1].travelTime - p.arrival;
}
return total;
}
static void calcDepartures(step[] steps){
int t = 0;
for (step s : steps){
if(s.departure < t){
s.departure = t;
}else{
t = s.departure;
}
t+=s.travelTime;
}
}
static void addPassengers(step[] steps, passenger[] passengers){
for (passenger p : passengers) {
if(steps[p.start].departure < p.arrival){
steps[p.start].departure = p.arrival;
}
steps[p.start].pickedUp++;
steps[p.dest].dropped++;
}
int load=0;
for (step s : steps){
load += s.pickedUp - s.dropped;
s.carried = load;
}
}
static void loadStuff(Scanner scan,step[] steps, passenger[] passengers){
for(int i=0;i<steps.length-1;i++){
steps[i] = new step();
steps[i].distance = scan.nextInt();
steps[i].departure = 0;
steps[i].travelTime = 0;
steps[i].carried = 0;
steps[i].pickedUp = 0;
steps[i].dropped = 0;
}
steps[steps.length-1] = new step();
for(int i=0;i<passengers.length;i++){
passengers[i] = new passenger();
passengers[i].arrival = scan.nextInt();
passengers[i].start = scan.nextInt()-1;
passengers[i].dest = scan.nextInt()-1;
}
}
static void printStations(step[] steps){
for(step s : steps){
System.out.println("-------");
System.out.println("departure : "+String.valueOf(s.departure));
System.out.println("distance : "+String.valueOf(s.distance));
System.out.println("travel time : "+String.valueOf(s.travelTime));
System.out.println("picked up : "+String.valueOf(s.pickedUp));
System.out.println("dropped : "+String.valueOf(s.dropped));
System.out.println("carried : "+String.valueOf(s.carried));
}
}
}
class passenger{
public
int arrival;
int start;
int dest;
}
class step{
public
int departure;
int distance;
int carried;
int pickedUp;
int dropped;
int travelTime;
}
class run implements Comparable<run>{
public
int station;
int deadline;
int carrying;
@Override public int compareTo(run r2){
return (this.carrying - r2.carrying);
}
}Problem solution in C++.
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
int dist[100100];
int late[100100];
int bin[100100];
int bout[100100];
int arrival[100100];
vector<long long> peop[100100];
long long ans;
void gen() {
cout << 100 << " " << 100 << " " << 1000 << endl;
for(int i = 0; i < 99; ++i) {
cout << rand() % 1000 << " ";
}
for(int i = 0; i < 100; ++i) {
int y = rand() % 100 + 1, x = rand() % y;
cout << rand() % (x * 1000 + 100) << " " << x << " " << y << endl;
}
exit(0);
}
struct st {
int i, j;
long long saved;
int spend;
st(int i, int j, long long saved, int spend) : i(i), j(j), saved(saved), spend(spend) {}
bool operator < (st a) const {
if (saved != a.saved) {
return saved < a.saved;
}
return spend < a.spend;
}
};
priority_queue<st> q;
int add(int i) {
if (i == n) return n;
int spend = 1000000000;
int j = i + 1;
if (dist[i]) {
spend = min(spend, dist[i]);
long long saved = 0;
for(j = i + 1; j <= n; ++j) {
--arrival[j];
saved += bout[j];
if (late[j] > arrival[j]) {
break;
}
spend = min(spend, arrival[j] - late[j] + 1);
}
if (j > n) j = n;
//cout << i << " = " << j << endl;
st w(i, j, saved, spend);
q.push(w);
for(int q = i + 1; q <= j; ++q) {
++arrival[q];
}
}
return j;
}
int main() {
//gen();
cin >> n >> m >> k;
--n;
for(int i = 0; i < n; ++i) {
cin >> dist[i];
}
for(int i = 0; i < m; ++i) {
int t, s, e;
cin >> t >> s >> e;
--s;
--e;
late[s] = max(late[s], t);
++bout[e];
peop[s].push_back(t);
}
late[n] = -1000000000;
long long nowt = 0, carry = 0;
for(int i = 0; i < n; ++i) {
arrival[i] = nowt;
for(int j = 0; j < peop[i].size(); ++j) {
if (peop[i][j] < nowt) {
ans += nowt - peop[i][j];
} else {
ans += carry * (peop[i][j] - nowt);
}
++carry;
nowt = max(peop[i][j], nowt);
}
ans += carry * dist[i];
nowt += dist[i];
carry -= bout[i + 1];
}
arrival[n] = nowt;
int cur = 0;
while(cur < n) {
cur = add(cur);
}
while(k && !q.empty()) {
st w = q.top();
q.pop();
if (w.spend >= k)
{
ans -= w.saved * k;
break;
}ans -= w.saved * w.spend;
k -= w.spend;
dist[w.i] -= w.spend;
for(int i = w.i + 1; i <= w.j; ++i) {
arrival[i] -= w.spend;
}
int x = w.i;
while(x < w.j)
{
x = add(x);
}
}
cout << ans << endl;
return 0;
}
Problem solution in C.
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int u;
int cur;
int w;
int c;
}node;
int last_arrive[100000], drop[100001], d[100000], heap_list[100001];
node heap[100001];
void heap_insert(node *elem, int *size)
{
(*size)++;
int index = (*size);
while( index > 1 && elem -> w < heap[index/2].w )
{
heap[index] = heap[index/2];
heap_list[heap[index].u] = index;
index /= 2;
}
heap[index] = (*elem);
heap_list[elem -> u] = index;
return;
}
void heap_update(node *elem, int *size)
{
int index = heap_list[elem -> u];
while( index * 2 <= *size && elem -> w > heap[index*2].w || index * 2 + 1 <= *size && elem -> w > heap[index*2+1].w )
{
index = ( index * 2 + 1 <= *size && heap[index*2].w > heap[index*2+1].w ) ? index * 2 + 1 : index * 2;
heap[index/2] = heap[index];
heap_list[heap[index].u] = index / 2;
}
heap[index] = (*elem);
heap_list[elem -> u] = index;
return;
}
void heap_read(int *size, node *ans)
{
(*ans) = heap[1];
int index = 1;
while( index * 2 < *size && heap[*size].w > heap[index*2].w || index * 2 + 1 < *size && heap[*size].w > heap[index*2+1].w )
{
index = ( heap[index*2].w > heap[index*2+1].w ) ? index * 2 + 1 : index * 2;
heap[index/2] = heap[index];
heap_list[heap[index].u] = index / 2;
}
heap[index] = heap[*size];
heap_list[heap[index].u] = index;
(*size)--;
return;
}
int main()
{
int n, m, k, x, y, z, total_use, last_time, heap_size, i;
long long start, ans;
node elem;
scanf("%d%d%d", &n, &m, &k);
for( i = 0 ; i < n - 1 ; i++ )
{
scanf("%d", d + i);
}
for( i = start = 0 ; i < m ; i++ )
{
scanf("%d%d%d", &x, &y, &z);
start += x;
if( x > last_arrive[y-1] )
{
last_arrive[y-1] = x;
}
drop[z-1]++;
}
for( i = n - 2 ; i >= 0 ; i-- )
{
drop[i] += drop[i+1];
}
for( i = ans = total_use = last_time = heap_size = 0 ; i < n ; i++ )
{
if(i)
{
total_use += d[i-1];
}
ans += ( drop[i] - drop[i+1] ) * (long long)last_time;
if( last_arrive[i] > last_time )
{
if(i)
{
elem.u = elem.cur = i;
elem.w = drop[i] - drop[i+1];
elem.c = last_arrive[i] - last_time;
heap_insert(&elem, &heap_size);
}
last_time = last_arrive[i];
}
}
elem.u = elem.cur = n - 1;
elem.w = drop[n-1] - drop[n];
elem.c = 100000000;
heap_insert(&elem, &heap_size);
if( total_use <= k )
{
printf("%lld", ans - start);
return 0;
}
k = total_use - k;
while(k)
{
elem = heap[1];
if( elem.c <= d[elem.cur-1] && elem.c <= k )
{
ans += elem.w * (long long)elem.c;
k -= elem.c;
d[elem.cur-1] -= elem.c;
heap_read(&heap_size, &elem);
}
else if( d[elem.cur-1] <= elem.c && d[elem.cur-1] <= k )
{
ans += elem.w * (long long)d[elem.cur-1];
k -= d[elem.cur-1];
elem.c -= d[elem.cur-1];
d[elem.cur-1] = 0;
for( ; elem.cur > 0 && !d[elem.cur-1] ; elem.cur-- );
if(elem.cur)
{
elem.w = drop[elem.cur] - drop[elem.u+1];
heap_update(&elem, &heap_size);
}
else
{
heap_read(&heap_size, &elem);
}
}
else
{
ans += elem.w * (long long)k;
k = 0;
}
}
printf("%lld", ans - start);
return 0;
}
0 Comments