1099. Packing Passengers
1 /*
2 题目大意是要求用两个飞机正好将所有的乘客全部载下，并且要求所要花费的费用最少
3 根据第一个条件，这道题就转化成了求解不定方程的问题
4 A机型的载客量*A机型的数量+B机型的载客量*B机型的数量=总乘客量-----（1）
5 使用扩展欧几里得算法可以求出一组基本解x，y使得一下的算式成立
6 A机型的载客量*X+B机型的载客量*Y=gcd（A机型的载客量，B机型的载客量）
7 X*=（总乘客量/gcd）
8 Y*=（总乘客量/gcd）
9 就求出了一组满足（1）的一组解
10 不定方程（1）的其他解可以通过（2），（3）求出
11 X=X+B的载客量/gcd（A的载客量，B的载客量）*t-------------（2）
12 Y=Y-A的载客量/gcd（A的载客量，B的载客量）*t-------------（3）
13 因为题目还有条件二，也就是需要让使用的费用最小
14 为了满足这个条件，就需要尽可能多的选择那些性价比高的机型，就是使得（2）或者（3）尽可能接近0
15 因为X,Y不能为负所以需要对求解出来的t进行取整修改
16
17 */
18 #include <iostream>
19 #include <math.h>
20 using namespace std;
21 long long exgcd( long long a, long long b, long long &x, long long &y)
22 {
23 if(b== 0)
24 {
25 x= 1;
26 y= 0;
27 return a;
28 }
29 long long r=exgcd(b,a%b,x,y);
30 long long t=x;
31 x=y;
32 y=t-a/b*y;
33 return r;
34 }
35 int main()
36 {
37 long long n,coa,cob,caa,cab;
38 cin>>n;
39 int t= 1;
40 while(n!= 0)
41 {
42 cin>>coa>>caa>>cob>>cab;
43 long long x,y;
44 long long r=exgcd(caa,cab,x,y);
45 if(n%r!= 0)
46 cout<< "Data set "<<t<< ": cannot be flown"<<endl;
47 else
48 {
49 x*=(n/r);
50 y*=(n/r);
51
52 int dela=ceil(( double)(-x)*r/cab); //如果b性价比高那么就将a机型飞机的数量减少，使得其尽可能的接近0
53 int delb=floor(( double)(y)*r/caa); //如果a性价比高那么就将b机型飞机的数量减少，使得其尽可能的接近0
54
55 int tem=coa*cab<=cob*caa?delb:dela; //选出性价比高的机型
56 x+=cab/r*tem;
57 y-=caa/r*tem;
58 cout<< "Data set "<<t<< ": "<<x<< " aircraft A, "<<y<< " aircraft B"<<endl;
59 }
60 cin>>n;
61 t++;
62 }
63 }
转载于:.html
