UVA 10090 Marbles 扩展欧几里得
2018-06-17 23:36:27来源:未知 阅读 ()
来源:http://www.cnblogs.com/zxhl/p/5106678.html
大致题意:给你n个球,给你两种盒子。第一种盒子每个盒子c1美元,可以恰好装n1个球;第二种盒子每个盒子c2元,可以恰好装n2个球。找出一种方法把这n个球装进盒子,每个盒子都装满,并且花费最少的钱。
假设第一种盒子买n1个,第二种盒子买n2个,则c1*n1+ c2*n2= n。由扩展欧几里得 ax+by= gcd(a,b)= g ,(a=n1,b=n2),如果n%g!=0,则方程无解。
ax+by=gcd(a,b)= g两边同时乘以n/g, 可以解出m1=nx/g, m2=ny/g,所以通解为m1=nx/g + bk/g, m2=ny/g - ak/g, 又因为m1和m2不能是负数,所以m1>=0, m2>=0,所以k的范围是 -nx/b <= k <= ny/a,且k必须是整数。
所以
k1=ceil(-nx/b)
k2=floor(ny/b)
如果k1>k2的话则k就没有一个可行的解,于是也是无解的情况。
想要花费的最少,也就相当于放一颗弹珠所花费的最少。即
c1/n1<?>c2/n2
c1*n2<?>c2*n1
如果c1*n2<c2*n1, 即第一种的盒子要更多。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long ll; ll exgcd(ll a, ll b, ll&x, ll&y) { if (b == 0) { x = 1; y = 0; return a; } ll r = exgcd(b, a%b, y, x); ll t = x; y = y - a/b*t; return r; } int main() { //freopen("in.txt","r",stdin); ll n; ll c1,n1,c2,n2; while(scanf("%lld",&n),n) { scanf("%lld%lld%lld%lld",&c1,&n1,&c2,&n2); ll x,y,a1,a2; ll g=exgcd(n1,n2,x,y); //printf("%lld\n%lld %lld\n",g,x,y); if(n%g!=0) { printf("failed\n"); continue; } ll k1=ceil(-n*x*1.0/n2); ll k2=floor(n*y*1.0/n1); if(k1>k2) { printf("failed\n"); continue; } if(c1*n2<c2*n1) { a1=n*x/g+n2*k2/g; a2=n*y/g-n1*k2/g; } else { a1=n*x/g+n2*k1/g; a2=n*y/g-n1*k1/g; } printf("%lld %lld\n",a1,a2); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:Codevs 1860 最大数
下一篇:2016.11.9 小测试
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
- J - Fire! UVA - 11624 2018-09-01
- uva11768 Lattice Point or Not 2018-08-14
- UVALive - 6434 (贪心) 2018-07-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash