喜欢就点个赞👍呗,每天都会更新哒~^-^
Problem:
将一组木棍随机打乱,然后你的任务是将其恢复成裁截前的状态(长度尽可能小),要求是所有裁截前的木棍长度相同,实际上的题目意思可以理解为将一组子节点回溯到根节点,然后找到所有同一级的节点相同的最小长度
Ideas:
从已经给出的所有木棍中找到最大的木棍,然后从该木棍长度开始,通过+1依次往上找,如果在所有节点都能够合成k组该长度的木棍(k=总长度/一根长度),那么结束寻找
(具体看代码实现)
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
int sticks[N];
bool st[N];
int sum, length;
bool dfs(int u, int cur, int start) { // 存储个数,当前正在合成的木棍长度,目前使用到的位置(作用是剪枝)
if(u * length == sum) return true; // 总长度达到说明可以
if(cur == length) return dfs(u + 1, 0, 0); // 存储数+1
for(int i = start; i < n; i ++ ) { // 如果start的不可以用,那么他前面的一定不可以用,因为是递减的
if(st[i]) continue;
int l = sticks[i];
if(cur + l <= length) { // 直接用(如果不行的话还有下一个i+1数继续使用)
st[i] = true;
if(dfs(u, cur + l, i + 1)) return true; // 如果继续使用可以完成,则找到最小长度,返回
st[i] = false; // 恢复
}
if(!cur || cur + l == length) return false; // 如果为空,则所有的都不合适,如果=length,则已经遍历过
int j = i + 1; // 当前使用过,后面肯定不能使用,因为满足下一次遍历的条件是cur+l<=length,到这一步说明已经>length了,或者说遍历过
while(j < n && sticks[j] == l) j ++ ;
i = j - 1;
}
return false;
}
void solve() {
while(cin >> n) {
if(n == 0) break;
sum = length = 0;
for(int i = 0; i < n; i ++ ) {
int l;
cin >> l;
sticks[i] = l;
sum += l;
length = max(length, l);
}
sort(sticks, sticks + n, greater<int>()); // 大到小排序
memset(st, 0, sizeof st);
while(1) {
if(sum % length == 0 && dfs(0, 0, 0)) {
cout << length << endl;
break;
}
length ++ ;
}
}
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
cout.tie(0);
int t = 1;
while(t -- ) {
solve();
}
}