AcWing 167. 木棒——大白话注释
原题链接
中等
作者:
zhy_AC
,
2024-03-27 19:27:02
,
所有人可见
,
阅读 3
#include <bits/stdc++.h>
using namespace std;
const int N = 64;
int sticks[N];
bool st[N];
int n,length,sum;
bool dfs(int a,int cur,int start) {
// 一个结束条件:找到了符合的
if(a * length == sum) return true;
// 如果当前的组合的木棍长度满足要求 就进行下一组
if(cur == length) return dfs(a+1,0,0);
// 从开始访问的下标开始遍历数组
for(int i = start;i < n;i++) {
// 因为不知道开始下标是在什么时候开始的,我们先来判断当前的木棒是否已经用过了
if(st[i]) continue; // 已经访问过了
// 如果当前的木棒可以组合 那么接着找到下一个
if(cur + sticks[i] <= length) {
st[i] = true;
if(dfs(a,cur + sticks[i],i+1)) return true;
st[i] = false;
}
// 这是将两个剪枝合并在了一起 一个是当木棒放在第一个的是否不满足条件
// 另一个是最后一个不满足的条件,及时止损
// 当进行到这一步骤时,说明当前的木棒是不满足条件的
if(!cur || cur + sticks[i] == length) return false;
// 以下就是将当前的不满足条件的木棒所有相同的木棒隔离掉
int j = i + 1;
while(j < n && sticks[j] == sticks[i]) j++;
i = j - 1;
}
return false;
}
int main(){
while(cin >> n, n) {
// 记录下当前轮的总长度(用来判断length是否合理)
sum = 0,length = 0;
for(int i = 0;i < n;i++) {
cin>>sticks[i];
sum += sticks[i];
length = max(length,sticks[i]);
}
// 将所有的木棍倒着排序(两种方法)
// sort(sticks,sticks + n);
// reverse(sticks,sticks + n);
sort(sticks,sticks + n,greater<int>());
// 将木棍的状态清空
memset(st,false,sizeof st);
// length 此时的长度是木棍中的最大值 然后遍历到第一个符合的长度
while(true) {
// 如果满足要求就进行dfs 遍历 参数(木棒的个数,木棍组合的当前长度,查找的初始下标)
if(sum % length == 0 && dfs(0,0,0)){
cout<<length<<endl;
break;
}
length++;
}
}
return 0;
}