USACO MAR09 Problem 'sandcas' Analysis

by Neal Wu

First, sort the A_i in non-decreasing order. It can be shown that to obtain an optimal solution, we can sort the B_i in non-decreasing order as well, and pair A_i with B_i. One way to prove this fact is by showing that if i < j and B_i > B_j, then swapping B_i and B_j will lead to a smaller total cost (by repeatedly applying this fact, we can show that a sorted list must be optimal). Once we are convinced of this fact, the implementation is quite simple:

#include <cstdio>
#include <algorithm>
using namespace std;

FILE *in = fopen ("sandcas.in", "r"), *out = fopen ("sandcas.out", "w");

const int MAXN = 25005;

int N, X, Y, total = 0, A [MAXN], B [MAXN];

inline int diff (int a, int b) {
    return a < b ? X * (b - a) : Y * (a - b);
}

int main () {
    fscanf (in, "%d %d %d", &N, &X, &Y);

    for (int i = 0; i < N; i++)
        fscanf (in, "%d %d", A + i, B + i);

    sort (A, A + N);
    sort (B, B + N);

    for (int i = 0; i < N; i++)
        total += diff (A [i], B [i]);

    fprintf (out, "%d\n", total);
    return 0;
}