解法:枚举
时间复杂度:$O(100 \times 100 \times 100)$
思路应该很简单,就是简单枚举,但是有一个坑就是为 $0$ 的情况。
当最佳混合饲料为 0 0 0 时,直接输出 0 0 0 0,因为后期是无法处理该类情况(Float Point Exception)。
其次求 k (份数)时,为避免除 0 的情况,应该做一下等价变换:
s1 = k * x
s2 = k * y ----> k = (s1 + s2 + s3) / (x + y + z);
s3 = k * z
(因为 s1 + s2 + s3 == 0 和 x + y + z == 0 已经处理过)
再做判断,是否成立
我在这里竟然卡了很久......。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4, INF = 1e9;
int x, y, z, xs, ys, zs;
int a[N], b[N], c[N];
int sucess(int c1, int c2, int c3)
{
if (c1 == 0 && c2 == 0 && c3 == 0) { // 0 38 7
return 0;
}
int p1 = c1 * a[0] + c2 * a[1] + c3 * a[2];
int p2 = c1 * b[0] + c2 * b[1] + c3 * b[2];
int p3 = c1 * c[0] + c2 * c[1] + c3 * c[2];
int k = (p1 + p2 + p3) / (x + y + z);
if (p1 == k * x && p2 == k * y && p3 == k * z) {
return k;
}
else {
return 0;
}
}
int main()
{
cin >> x >> y >> z;
for (int i = 0; i < 3; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
if (!x && !y && !z) {
puts("0 0 0 0 ");
return 0;
}
int mn = INF, cnt;
for (int i = 0; i < 100; ++i) {
for (int j = 0; j < 100; ++j) {
for (int k = 0; k < 100; ++k) {
int p;
if (p = sucess(i, j, k)) {
if (mn > i + j + k) {
mn = i + j + k;
xs = i, ys = j, zs = k;
cnt = p;
}
}
}
}
}
if (mn == INF) puts("NONE");
else {
cout << xs << ' ' << ys << ' ' << zs << ' ' << cnt;
}
return 0;
}
是success吧