程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2142 The Balance

POJ 2142 The Balance

編輯:C++入門知識

題意吧:一個家伙有一種天平,這種天平只有兩種重量的砝碼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(如果a<b,我們便交換a b),從這個式子中,我們可以輕易的發現:|x0+b/d*t|是單調遞增的,|y0-a/d*t|是單調遞減的,而由於我們規定了a>b,那麼減的斜率邊要大於增的斜率,於是整個函數減少的要比增加的快,但是由於絕對值的符號的作用,最終函數還是遞增的。也就是說,函數是凹的,先減小,再增大。那麼什麼時候最小呢?很顯然是y0-a/d*t==0的時候,於是我們的最小值|x|+|y|也一定是在t=y0*d/a附近了,我是在t點左右5個點的范圍內取最小的(據說左右一個點都可以,不過我試了一下wa了)。一般這樣的題目就多枚舉幾個點以防萬一嘛!!!

 

 

 

#include <iostream>   
#include <cstdio>   
#include <cstring>   
#include <string>   
#include <cstdlib>   
#include <cmath>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
#include <sstream>   
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<b)  
            f=1,swap(a,b);  
        int x,y,t,d;  
        d=ext_gcd(a,b,x,y);  
        x=x*c/d;    y=y*c/d;  
        t=y*d/a;  
        int x1,y1,Min=INF,xx,yy;  
        for(i=t-5;i<t+5;i++)//掃描周圍5個點   
        {  
            x1=abs(x+b/d*i);  
            y1=abs(y-a/d*i);  
            if(x1+y1<Min)  
            {  
                Min=x1+y1;  
                xx=x1;yy=y1;  
            }  
        }  
        if(f)  
            printf("%d %d\n",yy,xx);  
        else  
            printf("%d %d\n",xx,yy);  
    }  
    return 0;  
}  
  
/* 
 
*/  

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <sstream>
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<b)
            f=1,swap(a,b);
        int x,y,t,d;
        d=ext_gcd(a,b,x,y);
        x=x*c/d;    y=y*c/d;
        t=y*d/a;
        int x1,y1,Min=INF,xx,yy;
        for(i=t-5;i<t+5;i++)//掃描周圍5個點
        {
            x1=abs(x+b/d*i);
            y1=abs(y-a/d*i);
            if(x1+y1<Min)
            {
                Min=x1+y1;
                xx=x1;yy=y1;
            }
        }
        if(f)
            printf("%d %d\n",yy,xx);
        else
            printf("%d %d\n",xx,yy);
    }
    return 0;
}

/*

*/


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved