(UVA) Work Reduction - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1611

In this problem, we need to verify if it is better to contract a plan that reduce the current paperwork by one unit or half. The approach used by the solution below was Greedy.


import java.io.*;
import java.util.*;

class Main {
    public int targetWorkload;
    public int costUnit;
    public int costHalf;
    public String nameAgency;
    public Agency[] agencies;
    
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String line = br.readLine();
        int numTests = Integer.parseInt(line);
        for (int i = 0; i < numTests; i++) {
            line = br.readLine();
            String[] s = line.split("\\s");
            int startWorkload = Integer.parseInt(s[0]);
            targetWorkload = Integer.parseInt(s[1]);
            int numAgencies = Integer.parseInt(s[2]);
            
            agencies = new Agency[numAgencies];
            // read data for each agency
            for (int j = 0; j < numAgencies; j++) {
                line = br.readLine();
                s = line.split(":");
                nameAgency = s[0];
                
                String[] costs = s[1].split(",");
                costUnit = Integer.parseInt(costs[0]);
                costHalf = Integer.parseInt(costs[1]);
            
                int cost = 0;
                int currWorkload = startWorkload;
                while (currWorkload != targetWorkload) {
                    if (costUnit*(currWorkload+1)/2 < costHalf || currWorkload/2 < targetWorkload) {
                        cost += costUnit;
                        currWorkload -= 1;
                    }
                    else {
                        cost += costHalf;
                        currWorkload /= 2;
                    }
                }
                agencies[j] = new Agency(nameAgency, cost);
            }
            
            Arrays.sort(agencies);
            System.out.println("Case " + (i+1));
            for (int j = 0; j < numAgencies; j++) {
                System.out.println(agencies[j].name + " " + agencies[j].cost);
            }
        }
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
        
        System.exit(0);
    }
}

class Agency implements Comparable<Agency> {
    String name;
    int cost;
    
    public Agency(String name, int cost) {
        this.name = name;
        this.cost = cost;
    }
    
    public int compareTo(Agency a) {
        if (this.cost-a.cost == 0) {
            return this.name.compareTo(a.name);
        }
        
        return this.cost-a.cost;
    }
}