我来'Mixing Milk'

这又是一道ACM练习题，我的原则就是如果有时间，坚持每天考虑解决一道吸引我的ACM练习题，今天这道'Mixing Milk'题并不难，不过里面蕴含着一个基础的算法，毕竟对算法一类的知识生疏已久，今天就拿它做一次回顾吧！

这道'Mixing Milk'(1003)题目前在'在线测试'系统上的状态是474/1207=39.27%(即accepted/submit=ratio)，算是中等偏下难度的题了，照比我昨天作的1002题要简单(我的感觉)。起码看题之后思路清晰^_^。

'Mixing Milk'的题目大概是这样的，原题是英文，这里把它简单用中文描述一下：说牛奶制品行业是个薄利的边缘行业，那么这个行业靠什么赚钱呢？只有靠降低采购成本。现在有这么一家牛奶厂，每天的牛奶采购量为N(0 <= N <= 2,000,000)，而这些牛奶是从M(0 <= M <= 5,000)个奶农那采购的。当然奶农的牛奶的价格是不一致的，现在你是一个牛奶采购员，如果让你去到奶农那采购牛奶，如何能使采购量为N，而成本却最小，最后根据输入计算出这个成本值。输入输出的格式参见下面的例子：
输入：
100 5 — (1)
5 20 — (2)
9 40
3 10
8 80
6 30
输出：
630

简单说一下输入输出，输入部分第一行(1)，这里输入两个数，依次为牛奶厂一天的采购量以及奶农的个数；输入第二行至最后一行描述的都是奶农的信息，以(2)行为例：5 表示奶农牛奶代价，20表示这天奶农能够提供的最大牛奶量。输出就是采购的总成本。

其实很多人看到这个题就会马上有思路了，可能很多人都会有这样的大众想法："即将输入按照牛奶代价从低到高排序，然后从低的开始采购，直到采购足一天需要的奶量即可"。

这里一个让我回忆起大学曾经学过的诸多排序算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序等等，这里我选择了'插入排序'。也许很多人记不清插入排序是怎么回事儿了，见怪不怪，工作之后接触业务流程性的东西较多，而接触基本算法的机会则少只有少，大多数情况你只需要调用一个已经封装好的接口或着基础库即可。这里简单回顾一下'插入排序'算法，更精确的说法是'直接插入排序'。

[直接插入排序算法]
(1) 基本思想
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
(2) 算法描述
Input: R[1..N]

/* 对R[1..N]按递增序进行插入排序, R[0]是'哨兵'
Procedure InsertSort(Var R[N] : DataType);
Begin
  for I := 2 To N Do
  begin
     R[0] := R[I]; J := I – 1;
     While R[0] < R[J] Do /* 查找R[I]的插入位置 */
   begin
        R[J+1] := R[J]; /* 将大于R[I]的元素后移 */
        J := J – 1
     end
     R[J + 1] := R[0] ; /* 插入R[I] */
  end
End; /* InsertSort */

(3) 效率分析
由于算法中有一个嵌套选环，所以估算直接插入排序的时间复杂度为O(n^2)，是一个稳定的排序方法。

(4) 示例
初始序列 5| 2 8 9 7 1
i = 1           2 5| 8 9 7 1
i = 2           2 5 8| 9 7 1
i = 3           2 5 8 9| 7 1
i = 4           2 5 7 8 9| 1
i = 5           1 2 5 7 8 9|

这个算法实现起来并不很难，下面是'Mixing Milk'的解决方案(实现插入排序时没有使用'哨兵'，和上面的算法描述不完全一致)，已被在线测试系统Accepted，但未经雕琢过哟(感觉这道题算法重要，其他次之)，呵呵。

/*
* solution for 1003 in Problems Volume I
*/

#include
#include

int main(void) {
        int     total_milk_per_day;
        int     total_farmers;
        int     i;
        int     j;
        int     k;
        int     h;
        int     *price_amount_pair;
        int     total_price     = 0;
        int     cur_amount      = 0;

        /*
         * 获取牛奶厂每天需要牛奶量和供货商总数
         */
        (void)scanf("%d %d", &total_milk_per_day, &total_farmers);

price_amount_pair = (int*)malloc(total_farmers * 2 * sizeof(int));

        /*
         * 获取每个供货商的单价和提供量
         */
        for (i = 0; i < total_farmers; ++i) {
                k = 2 * i;
                (void)scanf("%d %d", price_amount_pair + k, price_amount_pair + k + 1);
        }

       /*
         * 利用插入排序使列表从前到后, 单价递增
         */
        for (i = 1; i < total_farmers; ++i) {
                for(j = 0; j < i; ++j) {
                        if (*(price_amount_pair + 2 * j) > *(price_amount_pair + 2 * i)) {
                                k = *(price_amount_pair + 2 * j);
                                h = *(price_amount_pair + 2 * j + 1);
                                *(price_amount_pair + 2 * j) = *(price_amount_pair + 2 * i);
                                *(price_amount_pair + 2 * j + 1) = *(price_amount_pair + 2 * i + 1);
                                *(price_amount_pair + 2 * i) = k;
                                *(price_amount_pair + 2 * i + 1) = h;
                        }

}
}

        for (i = 0; i < total_farmers; ++i) {
                if (cur_amount < total_milk_per_day) {
                        k = *(price_amount_pair + 2 * i + 1);
                        h = *(price_amount_pair + 2 * i);
                        if ((cur_amount + k) > total_milk_per_day) {
                                j = total_milk_per_day – cur_amount;
                                cur_amount += j;
                                total_price += (h * j);
                                break;
                        } else {
                                cur_amount += k;
                                total_price += (h * k);
                        }
                } else {
                        break;
                }
        }

        printf("%d\n", total_price);
        free(price_amount_pair);
        return 0;
}

发现做ACM练习题居然可以上瘾！^_^