2006年四月月 发布的文章

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

第一道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的练习是大有裨益的,上面的数制转换我以前也是很糊涂,就是因为在此题上的思考才让我’豁然开朗’^_^。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats