Protecting the Flowers (POJ 3262)

The key to this problem is not easy to find. The basic idea is we apply some measure on each cows and pick one cow with least or highest value of that measure at a time. Let's say we have cow $a$ and $b$, time to remove them are $l_a$ and $l_b$ and their damage abilities are $d_a$ and $d_b$. If we remove $a$ first, the total damage of flowers are $d_b\cdot l_a$, otherwise it will be $d_a\cdot l_b$. Obviously, if $d_b\cdot l_a \le d_a\cdot l_b$, we should remove $a$ first, or we should remove $b$. Transform the formular we get

$$\frac{l_a}{d_a} \le \frac{l_b}{d_b}$$

That inspire us use $\frac{l_i}{d_i}$ as the measure to pick cows. In practice, we do not calculate the fraction into double as it will lost precision. We use the first formular for comparation.

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

class Cow implements Comparable<Cow>{
    long x;
    long y;
    public Cow(long x, long y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Cow that) {
        Cow a = this;
        Cow b = that;
        long res = a.x * b.y - a.y * b.x;
        if (res > 0) return 1;
        else if (res < 0) return -1;
        else return 0;
    }
}
public class ProtectingTheFlowers {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();

        Cow[]cows = new Cow[N];
        long sum = 0;
        for (int i = 0; i < N; i++) {
            cows[i] = new Cow(in.nextLong(), in.nextLong());
            sum += cows[i].y;
        }

        Arrays.sort(cows);
        long cost = 0;

        for (int i = 0; i < N; i++) {
            sum -= cows[i].y;
            cost += sum * cows[i].x * 2;
        }
        System.out.println(cost);
    }
}