PKU 2124 The Balance 题解

这个题目第一眼看上去准备用数学方法解决
后来看上去数据范围比较小感觉直接枚举就可以了
然后写了个枚举的程序
ax+by=c
然后枚举a动态的保存min=a+b的最小值
当枚举的a>min的时候就停止就可以了
 1#include<stdio.h>
 2int main()
 3{
 4    int a,b,c,la,lb,x,y,ansx,ansy,l,min1,min2;
 5    while(scanf("%d%d%d",&a,&b,&c),a+b+c)
 6    {
 7        la=0;
 8        min1=1000000000;
 9        min2=1000000000;
10        while(1)
11        {
12            if(la>min1 ||la*a>min2)break;
13            l=a*la-c;
14            if(l>=0 && l%b==0)
15            {
16                lb=l/b;
17                x=la;y=lb;
18                if(lb<0)lb=-lb;
19                if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
20                    min1=la+lb;
21                    min2=la*a+lb*b;
22                    ansx=x;ansy=y;
23                }
24            }
25
26            l=c-a*la;
27            if(l>=0 && l%b==0)
28            {
29                lb=l/b;
30                x=la;y=lb;
31                if(lb<0)lb=-lb;
32                if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
33                    min1=la+lb;
34                    min2=la*a+lb*b;
35                    ansx=x;ansy=y;
36                }
37            }
38
39            l=c+a*la;
40            if(l>=0 && l%b==0)
41            {
42                lb=l/b;
43                x=la;y=lb;
44                if(lb<0)lb=-lb;
45                if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
46                    min1=la+lb;
47                    min2=la*a+lb*b;
48                    ansx=x;ansy=y;
49                }
50            }
51            la++;
52        }
53        printf("%d %d\n",ansx,ansy);
54    }
55    return 0;
56}
57

posted on 2008-07-19 19:23 gong 阅读(177) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜