首页 > 代码库 > 【USACO 3.2.4】饲料调配
【USACO 3.2.4】饲料调配
【描述】
农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成:大麦,燕麦和小麦。他知道自己的饲料精确的配比,在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料(同样都由三种麦子组成),然后将它们混合,来调配他的完美饲料。
给出三组整数,表示 大麦:燕麦:小麦 的比例,找出用这三种饲料调配 x:y:z 的饲料的方法。
例如,给出目标饲料 3:4:5 和三种饲料的比例:
1:2:3 3:7:1 2:1:2
你必须编程找出使这三种饲料用量最少的方案,要是不能用这三种饲料调配目标饲料,输出“NONE”。“用量最少”意味着三种饲料的用量(整数)的和必须最小。
对于上面的例子,你可以用8份饲料1,1份饲料2,和5份饲料3,来得到7份目标饲料:
8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)
表示饲料比例的整数以及目标饲料的都是小于100的非负整数。表示各种饲料的份数的整数,都小于100。一种混合物的比例不会由其他混合物的比例直接相加得到。
【格式】
PROGRAM NAME: ratios
INPUT FORMAT:
(file ratios.in)
Line 1: 三个用空格分开的整数,表示目标饲料
Line 2..4: 每行包括三个用空格分开的整数,表示农夫约翰买进的饲料的比例
OUTPUT FORMAT:
(file ratios.out)
输出文件要包括一行,这一行要么有四个整数,要么是“NONE”。前三个整数表示三种饲料的份数,用这样的配比可以得到目标饲料。第四个整数表示混合三种饲料后得到的目标饲料的份数。
【分析】
可以用枚举,不会超时,但是会很慢。
这里给出用高斯消元的做法,枚举目标量。然后判断是否有解就行了。
1 #include <cstdlib> 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <iostream> 7 #include <fstream> 8 using namespace std; 9 int data[100][100];10 int A[100][100];//求解 11 void init(int num);12 int gauss(int n);//高斯消元 13 void debug();14 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}15 int lcm(int a,int b){return a*b/gcd(a,b);}16 int main()17 {18 int i;19 //文件操作20 freopen("ratios.in","r",stdin);21 freopen("ratios.out","w",stdout); 22 memset(data,0,sizeof(data));23 //输入数据 24 scanf("%d%d%d",&data[3][0],&data[3][1],&data[3][2]);25 for (i=0;i<3;i++) scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);26 for (i=1;i<=100;i++)27 {28 init(i);//初始化 29 if (gauss(i)) return 0;30 }31 printf("NONE");32 return 0;33 }34 void init(int num)35 {36 int i,j;37 for (i=0;i<3;i++)//行列 38 for (j=0;j<3;j++) A[i][j]=data[j][i];39 A[0][3]=data[3][0]*num;40 A[1][3]=data[3][1]*num;41 A[2][3]=data[3][2]*num;42 43 }44 void debug()//调试 45 {46 int i,j;47 for (i=0;i<3;i++)48 {49 for (j=0;j<4;j++) printf("%d ",A[i][j]);50 printf("\n");51 }52 printf("\n");53 }54 int gauss(int m) 55 {56 int i=0,j=0,k,l,r,tmp,tmp1,tmp2,ans[5];57 memset(ans,0,sizeof(ans));58 while((i<3)&&(j<4))//i是行数,j当前需要消除的行数 59 {60 r=i;//绝对值最大 61 for(k=i+1;k<3;k++) if(A[k][j]>A[i][j]) r=k;62 if (r!=i) for(k=0;k<4;k++) swap(A[i][k],A[r][k]);63 64 if(A[i][j]!=0)65 {66 for(l=i+1;l<3;l++)67 if(A[l][j]!=0)68 {69 tmp=lcm(abs(A[l][j]),abs(A[i][j]));70 tmp1=tmp/A[i][j];71 tmp2=tmp/A[l][j];72 for(k=j;k<4;k++) A[l][k]=A[l][k]*tmp2-A[i][k]*tmp1;73 }74 i++;//行数 75 }76 j++; 77 }78 //debug();79 if(i==3)80 {81 for(i=2;i>=0;i--)82 {83 tmp=0;84 for(j=i+1;j<3;j++) tmp+=A[i][j]*ans[j];85 86 if((A[i][3]-tmp)%A[i][i]!=0) return false;87 ans[i]=(A[i][3]-tmp)/A[i][i];88 }89 90 if((ans[0]<0) || (ans[1]<0) || (ans[2]<0)) return 0;//只要 91 printf("%d %d %d %d\n",ans[0],ans[1],ans[2],m);92 return 1;93 }94 else return 0;95 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。