这题实际解不定方程:ax+by=c
只不过题目要求我们解出的x和y 满足|x|+|y|最小,当|x|+|y|相同时,满足|ax|+|by|最小。
首先用扩展欧几里德,很容易得出x和y的解。
一开始不妨令a>b,若a<=b,则交换a和b。
设d=gcd(a,b),最终的
则x=x0+b/d*t,y=y0-a/d*t
z=|x|+|y|=|x0+b/d*t|+|y0-a/d*t|
实际上就是求z=|a1*t+c1|+|c2-a2*t|在t取何值时最小。(a2>a1)
首先由不定方程ax+by=c,a>0,b>0,c>0可知,x和y只有下述三种情况:
x>0,y<0; x<0,y>0; x>0,y>0;
那么对t分类讨论,得出:
1.t<min(-c1/a1,c2/a2),z=-(a1+a2)t+c2-c1,单调减
2.-c1/a1<t<c2/a2,z=(a1-a2)t+c1+c2,单调减
3.t>max(-c1/a1,c2/a2),z=(a1+a2)t+c1-c2,单调增
这样,我们知道当z取最小值时,t=c2/a2=y0/(a/d)=y0*d/a 附近
接着只要在t附近几个比较一下取最小值即可。
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm> using namespace std;
int a,b,c; int exgcd(int a,int b,int &x,int &y){
if(b==){
x=;
y=;
return a;
}
int d=exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}
int main()
{
int number,mass;
while(scanf("%d%d%d",&a,&b,&c)!=EOF){
if(a== && b== && c==)
break;
bool flag=false;
if(a<b){
flag=true;
int tmp=a;
a=b;
b=tmp;
}
int x0,y0,x,y;
int d=exgcd(a,b,x,y);
int s1=b/d,s2=a/d;
x=x*(c/d);
y=y*(c/d);
int t=y*d/a; number=abs(x)+abs(y);
mass=abs(x)*a+abs(y)*b;
int xx,yy,ansx=x,ansy=y;
for(int i=t-;i<=t+;i++){
xx=x+s1*i;
yy=y-s2*i;
if(abs(xx)+abs(yy)<number){
number=abs(xx)+abs(yy);
mass=abs(xx)*a+abs(yy)*b;
ansx=xx;
ansy=yy;
}
else if(abs(xx)+abs(yy)==number && abs(xx)*a+abs(yy)*b<mass){
mass=abs(xx)*a+abs(yy)*b;
ansx=xx;
ansy=yy;
}
}
if(!flag)
printf("%d %d\n",abs(ansx),abs(ansy));
else
printf("%d %d\n",abs(ansy),abs(ansx));
}
return ;
}
POJ 2142 The Balance (解不定方程,找最小值)的更多相关文章
-
POJ.2142 The Balance (拓展欧几里得)
POJ.2142 The Balance (拓展欧几里得) 题意分析 现有2种质量为a克与b克的砝码,求最少 分别用多少个(同时总质量也最小)砝码,使得能称出c克的物品. 设两种砝码分别有x个与y个, ...
-
POJ - 2142 The Balance(扩展欧几里得求解不定方程)
d.用2种砝码,质量分别为a和b,称出质量为d的物品.求所用的砝码总数量最小(x+y最小),并且总质量最小(ax+by最小). s.扩展欧几里得求解不定方程. 设ax+by=d. 题意说不定方程一定有 ...
-
poj 2142 The Balance
The Balance http://poj.org/problem?id=2142 Time Limit: 5000MS Memory Limit: 65536K Descripti ...
-
POJ 2142 - The Balance [ 扩展欧几里得 ]
题意: 给定 a b n找到满足ax+by=n 的x,y 令|x|+|y|最小(等时令a|x|+b|y|最小) 分析: 算法一定是扩展欧几里得. 最小的时候一定是 x 是最小正值 或者 y 是最小正值 ...
-
POJ 2142 The Balance(exgcd)
嗯... 题目链接:http://poj.org/problem?id=2142 AC代码: #include<cstdio> #include<iostream> using ...
-
POJ 2142 The Balance【扩展欧几里德】
题意:有两种类型的砝码,每种的砝码质量a和b给你,现在要求称出质量为c的物品,要求a的数量x和b的数量y最小,以及x+y的值最小. 用扩展欧几里德求ax+by=c,求出ax+by=1的一组通解,求出当 ...
-
POJ 2142 The balance | EXGCD
题目: 求ax+by=c的一组解,使得abs(x)+abs(y)尽量小,满足前面前提下abs(ax)+abs(by)尽量小 题解: exgcd之后,分别求出让x尽量小和y尽量小的解,取min即可 #i ...
-
poj 2456 Aggressive cows &;&; nyoj 疯牛 最大化最小值 二分
poj 2456 Aggressive cows && nyoj 疯牛 最大化最小值 二分 题目链接: nyoj : http://acm.nyist.net/JudgeOnline/ ...
-
POJ 2142:The Balance_扩展欧几里得(多组解)
先做出两个函数的图像,然后求|x|+|y|的最小值.|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值应该在t零点附近(在斜率大的那条折线的零点附近,可以观察出 ...
随机推荐
-
OD调试17
程序先出现一个nag 然后出现主窗口 然后出现第二个nag窗口 我们查个壳 没有壳 那就载入OD看看,继续用调用堆栈的方法 发现一直执行用的都是这一个call,最后执行到程序结束.之 ...
-
用max-width来防止图片溢出---不兼容ie6-----将max-width设置成父元素的宽度,当图片过大时会换行,以及限制图片的宽度。但是如果使用table,仍然可能超出限制。
img{ max-width:100%; height:auto; } 如题.
-
SRM 601(1-250pt,500pt)
DIV1 250pt 题意:有很多袋子,里面装有苹果和橘子(也可能没有),给出每个袋子里有多少个苹果,多少个橘子.如果每个袋子里含有水果的总数都不小于x个,则可以从每个袋子里都拿出x个水果(拿出苹果和 ...
-
能够兼容ViewPager的ScrollView
/** * 能够兼容ViewPager的ScrollView * @Description: 解决了ViewPager在ScrollView中的滑动反弹问题 */ public class Scrol ...
-
认识WinDbg
WinDbg学习笔记(一)--认识WinDbg 一.前言 本人学习WinDbg已经有好几天了,虽说技术掌握的还不太熟练,不过也总算是入门了在学习WinDbg的过程中,觉得WinDbg真的比Oll ...
-
python and or用法
and 和 or 是python的两个逻辑运算符,可以使用and , or来进行多个条件内容的判断.下面通过代码简单说明下and or的用法: 1. or:当有一个条件为真时,该条件即为真.逻辑图如 ...
-
状压dp入门第一题 poj3254
题目链接 http://poj.org/problem?id=3254 转自http://blog.csdn.net/harrypoirot/article/details/23163485 #inc ...
-
Day11 空时编码理论之正交空时分组码和垂直分层空时编码
空时编码的用途: 一是获得分集增益(STBC,通过不同的发射天线发送相同传输信号的不同副本,实现空间分集,提高传输质量): 二是获得复用增益(V-BLAST在同一时隙,将不同的符号通过不同的天线发射出 ...
-
java 应用程序的编译和运行
1.java 文件的编译和执行步骤. 第一步:使用编辑器编辑 后缀为java的文件,里面包含主类(包含 main()函数), 源文件的命名规则是,如果源文件中有多个类,那么只能有一个类是public ...
-
HDU 4656 Evaluation(MTT)
题意 \(x_k=bc^{2k}+d\) \(\displaystyle F(x)=\sum_{i=0}^{n-1}a_ix^i\) 给定 \(\{a\},b,c,d,n\) ,求 \(F(x_0), ...