含温馨提示的题解
2024-04-16 15:26:09
发布于:上海
8阅读
0回复
0点赞
第二题:
读题:
鸡兔同笼,n辆车,m个轮子,问电瓶车、三轮车、汽车各多少
初级思路提供:
不要以为三层for暴力破解能过,我两层优化求汽车都过不了
参考代码:(TLE一个,最高复杂度25/6*1010)
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=m/2;i++){
for(int j=0;j<=m/3-i*2;j++){
int k=n-i-j;
//cout<<i<<" "<<j<<" "<<k<<endl;
if(k>=0&&2*i+3*j+4*k==m){
cout<<i<<" "<<j<<" "<<k<<endl;
return 0;
}
}
}
cout<<"-1 -1 -1"<<endl;
return 0;
}
高级思路提供:
可以根据解不定方程的办法,把n和m作为常数考虑
先列出等量关系
然后根据等量关系1把k换做i和j表示
接着用等量关系2再把k换成i和j表示,以便于待会儿把j换做i表示
最后根据新得到的k=......的两个等量关系得到i和j两者等量关系
代码:
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=m/2;i++){
int j=4*n-m-2*i;
if(j>=0){
int k=n-i-j;
if(k>=0&&i*2+j*3+k*4==m){
cout<<i<<" "<<j<<" "<<k<<endl;
return 0;
}
}
}
cout<<"-1 -1 -1"<<endl;
return 0;
}
这里空空如也
有帮助,赞一个