60 lines
1.6 KiB
C++
60 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
//https://www.luogu.com.cn/problem/P2036
|
||
|
||
//定义长长整为ll,用着方便
|
||
typedef long long ll;
|
||
|
||
//结构体:配料
|
||
struct ingredient {
|
||
ll S;//酸度
|
||
ll B;//甜度
|
||
} x[11]; //配料数最多是10个，就算是把0不要了，11个也足够了
|
||
|
||
int n;
|
||
ll ans = 10000001; //酸度和甜度的最小的绝对差
|
||
ll S_RESULT = 1; //酸度乘法结果
|
||
ll B_RESULT = 0; //甜度加法结果
|
||
|
||
//深度优先搜索
|
||
void dfs(int i) {
|
||
//并不是到n停止，注意一下,要到4号小箱子啊！
|
||
if (i == n + 1) {
|
||
//如果一个都没选就不存最小值，否则会出现ans=0的情况
|
||
if (S_RESULT == 1 && B_RESULT == 0) {
|
||
return;
|
||
}
|
||
//本轮走到头与其它各轮次的结果对比，哪个小就保留哪个
|
||
ans = min(ans, abs(S_RESULT - B_RESULT));
|
||
return;
|
||
}
|
||
//如果本轮要x[i]这种配料
|
||
S_RESULT *= x[i].S; //酸度乘法结果
|
||
B_RESULT += x[i].B; //甜度加法结果
|
||
//探索下一个配料!
|
||
dfs(i + 1);
|
||
|
||
//如果本轮不要x[i]这种配料
|
||
S_RESULT /= x[i].S;//回溯
|
||
B_RESULT -= x[i].B;//回溯
|
||
//直接跳到下一种配料
|
||
dfs(i + 1);
|
||
}
|
||
|
||
int main() {
|
||
//读入输出优化的强迫症
|
||
ios::sync_with_stdio(false);
|
||
//可支配的配料数
|
||
cin >> n;
|
||
//输入配料数据
|
||
for (int i = 1; i <= n; i++)
|
||
cin >> x[i].S >> x[i].B; //先酸度，后甜度
|
||
//从第一个配料开始吧！
|
||
dfs(1);
|
||
|
||
//输出:酸度和甜度的最小的绝对差。
|
||
cout << ans;
|
||
return 0;
|
||
} |