百钱买百鸡但不完全是百钱买百鸡
2024-07-16 20:51:40
发布于：广东
提醒一下刷到这题的朋友,不要暴力枚举,会TLE！
刷到这道题的时候，发现和我平时 在CSDN抄的题解上找不到 做的百钱买只因百鸡不一样。原来是题目改了，改成了N钱买N只因鸡。同时，因为 对于100%的数据0<n<100000000(一亿 别数有多少个零了，反正很多)所以暴力枚举肯定不行，会白给TLE(运行超时)的。
为了不超时，我们就要简化我们的算法。 ← 重点！！！
已知(设 公只因有i只，母只因有j只，小只因有k只)
- i+j+k=n
- 5i+3j+k/3=n
根据已知条件，我们先消掉k算出7i+4j=n
再进一步简化，我们可以根据i直接算出j：
for(int i=0;i<n/7;i++){//对，你没看错，只需要遍历 i
j=(n-7*i)/4;//总数减去公只因数再除以4求出母只因
k=n-(n-7*i)/4;//总数减去公只因数和母只因数求出小只因数
}
把暴力枚举简化之后，差不多算法的主体就完成了
加个输入、判断和输出就能AC了
#include<iostream>
using namespace std;
int main(){
int n,count=0;
cin>>n;
for(int i=0;i<=n/7;i++){
int j=(n-7*i)/4;
if((n-7*i)%4==0&&(n-i-j)%3==0)
count++;
}
cout<<count;
return 0;
}
做题解真的好辛苦(>_<)，给个赞吧
全部评论 8
66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
3天前 来自 上海
0
有帮助，赞一个