POJ 2142 The Balance (解不定方程,找最小值)

时间:2022-09-19 08:28:27

这题实际解不定方程: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 (解不定方程,找最小值)的更多相关文章

  1. POJ&period;2142 The Balance &lpar;拓展欧几里得&rpar;

    POJ.2142 The Balance (拓展欧几里得) 题意分析 现有2种质量为a克与b克的砝码,求最少 分别用多少个(同时总质量也最小)砝码,使得能称出c克的物品. 设两种砝码分别有x个与y个, ...

  2. POJ - 2142 The Balance(扩展欧几里得求解不定方程)

    d.用2种砝码,质量分别为a和b,称出质量为d的物品.求所用的砝码总数量最小(x+y最小),并且总质量最小(ax+by最小). s.扩展欧几里得求解不定方程. 设ax+by=d. 题意说不定方程一定有 ...

  3. poj 2142 The Balance

    The Balance http://poj.org/problem?id=2142 Time Limit: 5000MS   Memory Limit: 65536K       Descripti ...

  4. POJ 2142 - The Balance &lbrack; 扩展欧几里得 &rsqb;

    题意: 给定 a b n找到满足ax+by=n 的x,y 令|x|+|y|最小(等时令a|x|+b|y|最小) 分析: 算法一定是扩展欧几里得. 最小的时候一定是 x 是最小正值 或者 y 是最小正值 ...

  5. POJ 2142 The Balance(exgcd)

    嗯... 题目链接:http://poj.org/problem?id=2142 AC代码: #include<cstdio> #include<iostream> using ...

  6. POJ 2142 The Balance【扩展欧几里德】

    题意:有两种类型的砝码,每种的砝码质量a和b给你,现在要求称出质量为c的物品,要求a的数量x和b的数量y最小,以及x+y的值最小. 用扩展欧几里德求ax+by=c,求出ax+by=1的一组通解,求出当 ...

  7. POJ 2142 The balance &vert; EXGCD

    题目: 求ax+by=c的一组解,使得abs(x)+abs(y)尽量小,满足前面前提下abs(ax)+abs(by)尽量小 题解: exgcd之后,分别求出让x尽量小和y尽量小的解,取min即可 #i ...

  8. poj 2456 Aggressive cows &amp&semi;&amp&semi; nyoj 疯牛 最大化最小值 二分

    poj 2456 Aggressive cows && nyoj 疯牛 最大化最小值 二分 题目链接: nyoj : http://acm.nyist.net/JudgeOnline/ ...

  9. POJ 2142&colon;The Balance&lowbar;扩展欧几里得&lpar;多组解&rpar;

    先做出两个函数的图像,然后求|x|+|y|的最小值.|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值应该在t零点附近(在斜率大的那条折线的零点附近,可以观察出 ...

随机推荐

  1. OD调试17

    程序先出现一个nag 然后出现主窗口 然后出现第二个nag窗口        我们查个壳   没有壳 那就载入OD看看,继续用调用堆栈的方法 发现一直执行用的都是这一个call,最后执行到程序结束.之 ...

  2. 用max-width来防止图片溢出---不兼容ie6-----将max-width设置成父元素的宽度,当图片过大时会换行,以及限制图片的宽度。但是如果使用table,仍然可能超出限制。

    img{ max-width:100%;  height:auto; } 如题.

  3. SRM 601&lpar;1-250pt&comma;500pt&rpar;

    DIV1 250pt 题意:有很多袋子,里面装有苹果和橘子(也可能没有),给出每个袋子里有多少个苹果,多少个橘子.如果每个袋子里含有水果的总数都不小于x个,则可以从每个袋子里都拿出x个水果(拿出苹果和 ...

  4. 能够兼容ViewPager的ScrollView

    /** * 能够兼容ViewPager的ScrollView * @Description: 解决了ViewPager在ScrollView中的滑动反弹问题 */ public class Scrol ...

  5. 认识WinDbg

    WinDbg学习笔记(一)--认识WinDbg 一.前言    本人学习WinDbg已经有好几天了,虽说技术掌握的还不太熟练,不过也总算是入门了在学习WinDbg的过程中,觉得WinDbg真的比Oll ...

  6. python and or用法

    and 和 or 是python的两个逻辑运算符,可以使用and , or来进行多个条件内容的判断.下面通过代码简单说明下and  or的用法: 1. or:当有一个条件为真时,该条件即为真.逻辑图如 ...

  7. 状压dp入门第一题 poj3254

    题目链接 http://poj.org/problem?id=3254 转自http://blog.csdn.net/harrypoirot/article/details/23163485 #inc ...

  8. Day11 空时编码理论之正交空时分组码和垂直分层空时编码

    空时编码的用途: 一是获得分集增益(STBC,通过不同的发射天线发送相同传输信号的不同副本,实现空间分集,提高传输质量): 二是获得复用增益(V-BLAST在同一时隙,将不同的符号通过不同的天线发射出 ...

  9. java 应用程序的编译和运行

    1.java 文件的编译和执行步骤. 第一步:使用编辑器编辑  后缀为java的文件,里面包含主类(包含 main()函数), 源文件的命名规则是,如果源文件中有多个类,那么只能有一个类是public ...

  10. 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), ...