POJ 2142 The Balance - c++编程基础

TOP

POJ 2142 The Balance

2014-11-23 21:12:45 来源: 作者: 【大中小】浏览:13次

题意吧：一个家伙有一种天平，这种天平只有两种重量的砝码a和b，现在要称出重量为c的物品，问你至少需要多少a和b，答案需要满足a的数量加上b的数量和最小，并且他们的重量和也要最小。（两个盘都可以放砝码）

分析：
这题我刚刚开始还以为是动规或者搜索，也算是碰了一鼻子的灰吧。
假设a砝码我们用了x个，b砝码我们用了y个。那么天平平衡时，就应该满足ax+by==c。x,y为正时表示放在和c物品的另一边，为负时表示放在c物品的同一边。
于是题意就变成了求|x|+|y|的最小值了。x和y是不定式ax+by==c的解。
刚刚上面已经提到了关于x,y的所以解的同式，即
x=x0+b/d*t
y=y0-a/d*t
你是不是下意识的想要穷举所有解，取|x|+|y|最小的？显然是行不通的，仔细分析：|x|+|y|==|x0+b/d*t|+|y0-a/d*t|，我们规定a>b(如果ab，那么减的斜率边要大于增的斜率，于是整个函数减少的要比增加的快，但是由于绝对值的符号的作用，最终函数还是递增的。也就是说，函数是凹的，先减小，再增大。那么什么时候最小呢？很显然是y0-a/d*t==0的时候，于是我们的最小值|x|+|y|也一定是在t=y0*d/a附近了，我是在t点左右5个点的范围内取最小的(据说左右一个点都可以，不过我试了一下wa了)。一般这样的题目就多枚举几个点以防万一嘛！！！

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
using namespace std;  
  
typedef long long LL;  
const int N=10010;  
const LL II=100000000;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
int ext_gcd(int a,int b,int &x,int &y)  
{  
    int t,ret;  
    if(!b)  
    {  
        x=1,y=0;  
        return a;  
    }  
    ret=ext_gcd(b,a%b,x,y);  
    t=x,x=y,y=t-a/b*y;  
    return ret;  
}  
  
int gcd(int m,int n)  
{  
    int t;  
    while(n)  
    {   t=m%n;  m=n;    n=t;    }  
    return m;  
}  
  
int main()  
{  
    int i,j,a,b,c;  
    while(scanf("%d%d%d",&a,&b,&c)&&(a+b+c))  
    {  
        int f=0;//标记ab交换   
        if(a
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N=10010;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

int ext_gcd(int a,int b,int &x,int &y)
{
    int t,ret;
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ret=ext_gcd(b,a%b,x,y);
    t=x,x=y,y=t-a/b*y;
    return ret;
}

int gcd(int m,int n)
{
    int t;
    while(n)
    {	t=m%n;	m=n;	n=t;	}
    return m;
}

int main()
{
    int i,j,a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)&&(a+b+c))
    {
        int f=0;//标记ab交换
        if(a


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVa 10692 - Huge Mods（指数循环..	下一篇：hdu-4632-Palindrome subsequence..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: