这又是一道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练习题居然可以上瘾！^_^

说来惭愧，今天才真正做过一道ACM练习题。自从上个月发现我的母校上有ACM的在线测试站点，我就下决心好好潜心做题，一来提高一下自己解决问题的能力，一方面也想在算法方面多实践实践，而且每天都花一定时间写程序还可以锻炼自己的思维能力。总而言之，由于项目繁忙以至直到今天才开始做第一道ACM练习题，做题的过程’坎坷不平’，让我印象深刻亚!^_^

有人会说：’ACM’中的题都是不实用的，没有实际意义。我之前也曾经是这么想的。不过今天的作题过程让我完全推翻了以前的想法，我发现ACM的习题是很能锻炼个人的思维能力、编程能力的。就拿今天我做的这道看似简单的问题，实际上其背后也蕴含着很多基础理论，如果没有很好的理论基础做后盾，我相信很多人都会在这道题上’碰个头破血流’。

在看题之前我不能不说母校的那套ACM在线测试系统，你只需要做一个简单的注册，即可使用该系统，目前系统支持C/C++良种语言的提交代码，系统会自动对你的源码进行编译、运行和测试，并在你提交代码后大约5分钟内给出你结果。系统提供一个’Problem Set’供大家解决，目前这个’Problem Set’中有超过1000个题目，有兴趣的人大可以去试试，没有什么奖励，就是兴趣而已，特别是像我们这些已经毕业的人更不可能以参加ACM竞赛为目标了^_^。该站点还提供一个论坛，供解决问题者交流心得。

解决ACM练习题不同于开发商业软件，所有的题都有明确的’输入范围’，所以在程序里无需’断言’等’Precondition Check’，对异常的处理也无需太过考虑。ACM主要锻炼的是你的思考过程、算法设计能力以及快速解决问题的能力。要想达到一个很高的层次，需经过大量的训练才可以。

大多数人在解决’Problem Set’中的问题时都是从Problems Volume I开始，我也不例外。Volume I的第一道题1001我觉得是个举例，没必要对它进行过多研究。看完1001后，进入1002，这也是本文想说的一个实例。

1002问题的题目为’A+B+C’，具体内容描述如下：
"For each pair of integers A B and C ( -2^31 <= A, B, C<= 2^31-1 ), Output the result of A+B+C on a single line. "

Sample Input
1 2 3
3 4 3

Sample Output
6
10

题目看起来很简单，不细心的人很可能把1001的解决方案直接拿过来套用，这样当然是错的了。那么这道题到底需要什么知识呢？我们大致来分析一下：这道题其实就是一个加法题，唯一让大家担心的就是几个输入数据的范围照比1001的[1, 10]要扩大了，扩大到无符号整型范围，这样就导致我们必须考虑一个问题：那就是’溢出’问题。很多人都能想到这，那么如何解决这一问题呢？

首先拿出一个方案看看可行不：
[方案一]
#include <stdio.h>

int main(void) {
        int       a;
        int       b;
        int       c;

        while (scanf("%d %d %d", &a, &b, &c) == 3) {
                printf("%d\n", a + b + c);
        }
        return 0;
}

首先将a, b, c定义为int(一般系统的实现都把int默认为unsigned int)可以满足输入需求，但是a + b + c显然可能会溢出，导致结果不正确。

[方案2]
既然直接使用a + b + c，并使用%d输出会溢出，那么我们用一个更大的数据类型来存储相加后的结果呢，这样可行么？不妨看看。
#include <stdio.h>

int main(void) {
        int  a;
        int  b;
        int  c;
 long long rv;

        while (scanf("%d %d %d", &a, &b, &c) == 3) {
  rv = a + b + c;
                printf("%lld\n", rv);
        }
        return 0;
}

我们用2147483647 1 1测试后发现结果为-2147483647。显然这一方案也不成，不过我们得知道为什么不成才能继续给出新的方案。这个方案就在于rv = a + b + c这条语句上，这里有一个原则我们必须先明了，那就是ANSI C在’一般算术运算’的时候采用’值保留’的原则，这区别于K&R C的’无符号保留’原则，我们下面具体分析一下：
a = 2147483647(d) = 0x7FFFFFFF;
b = 1(d) = 0×00000001;
c = 1(d) = 0×00000001;
a + b + c = 0×80000001;
那么0×80000001转为为十进制整型值是多少呢？这里有人认为是-1(d)，这当然不对，我们该如何通过这个0×80000001找到其对应的十进制值呢？我们知道采用二进制补码方式正整数d对应的-d的计算方法为：-d = (~d + 1); 所以我们通过-d求d就可以这样做：
0×80000001 – 1(d) = 0×80000001 – 0×00000001 = 0×80000000;
0×80000000逐位取反得到0x7FFFFFFF, 而0x7FFFFFFF = 2147483647(d)，所以我们得出0×80000001 = -2147483647(d)。
这样rv = a + b + c就变成了rv = -2147483647(d)，同样是’值保留’，那么一个long long类型的rv转换为-2147483647(d)后的’位模式’该是什么样子的呢？其计算方法为(~2147483647(d) + 1)，即(~0x000000007FFFFFFF + 1)，即0xFFFFFFFF80000001，这是个负数，我们要得到其真实值，还得需像上面的计算方式计算：
0xFFFFFFFF80000001 – 1(d) = 0xFFFFFFFF80000001 – 0×0000000000000001 = 0xFFFFFFFF80000000;
0xFFFFFFFF80000000逐位取反得到0x000000007FFFFFFF, 而0x000000007FFFFFFF = 2147483647(d)，所以rv = -2147483647(d)

[方案三]
我们知道上面的问题是由于在不同类型间依照’值保留’原则转型造成的，那么我们大可这么做：
int main(void) {
        long long       a;
        long long       b;
        long long       c;

        while (scanf("%lld %lld %lld", &a, &b, &c) == 3) {
                printf("%lld\n", a + b + c);
        }
        return 0;
}

在在线测试系统提交后，状态’Accepted’，至此问题解决，当然问题的解决方法可以有很多种，我想这种是最简单的方法之一了。

怎么样，其实每道ACM题的背后都会有一些’基础理论’在支撑，所以多多做ACM的练习是大有裨益的，上面的数制转换我以前也是很糊涂，就是因为在此题上的思考才让我’豁然开朗’^_^。