我来'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练习题居然可以上瘾!^_^
评论