又是一部’妈妈再爱我一次’的影片，煽情之处此起彼伏，相信看过这部片子的人%80会’留下’热泪，呵呵，不好意思，我也是这%80的人当中的一员，不过’留泪’也代表你完全入戏了。看完这部戏的最大感受就是’这是一次心灵的净化，人的本性的释放’。

本来昨天要看张元新作’看上去很美’的，记得上次在电影院看’纳尼亚传奇’之前，有两个新片介绍，一个是’一球成名’，另一个就是’看上去很美’，电影院中的观众都被那个’调皮而又充满叛逆色彩、灵性十足的小家伙儿方枪枪吸引了，都在讨论着要看这部片的想法。不过昨天的计划被GF打乱了，她非要看’暖春’说后者感人。就这样我们开始了’一把鼻涕一把泪’的观看过程。

这部剧与’妈妈再爱我一次’最最相像’的一点就是小花的’哭声’，是那么的有感染力，与其说是片子中的剧情让人流泪，倒不如说是小花的哭声把人们感染了。其实我感觉拍摄这种充满情感元素在其中的电影是中国电影的特色，中国从旧社会过渡到目前的状态，这期间又太多的素材了。有人说这是拿中国的贫穷落后去吸引外国人的目光，我却我这么认为，像’暖春’这部片子，我想即使是目前的中国也会存在这样的现象的，承认自己的落后，迎头赶上才是我们需要的，而不是藏着掖着，生怕别人知道自己有多落后。有些跑题了。影片真正能打动人的是蕴含在其中的情感，而这种情感是人类共有的，不分肤色、不分国度，我想这也是同题材经典影片’那人.那山.那狗’在国外成功的原因吧。

今天查资料才知道’暖春’这部影片是2004年第27届百花奖优秀故事片奖得主，饰演该片中’爷爷’角色的演员田成仁相信大家都是耳熟能详的，这位老人演技自不必说，其表现出的那种真挚的、善良的感情，相信打动的不只是一代人了。饰演小花的张妍则是从一千多个孩子中脱颖而出的佼佼者，看完影片的人对其印象应该尤为深刻，一个初出茅庐的小女孩能把小花这个角色演绎得如此感情丰富，有感染力已实属不易。

这里向大家推荐这部影片，因为它给了我们一次净化心灵的机会，让心灵底处的人的本性得以释放，让我们重新审视这个物欲横流的社会，这难道不是很难得的吗！

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