小木棍
这道题时间限制极为严格(260ms),我们只能使用静态数组
先看思路,这道题本质上就是把这些数据分为几个小集合,使这些小集合的元素和相等
要我们求出最小和
我们定义L为目标长度,len为当前长度,假设数组为nums
首先我们需要排序,推荐从大到小,那么L肯定大于或等于nums[0]
所以,我们求最小值就从nums[0]开始
len也推荐从nums[0]开始,因为越长的木棍意味着越少的选择
但是,由于时间极为苛刻,我们必须采取剪枝,除去一些不必要的遍历
1.当总长度(sum)除以L不是整数时,直接跳过
2.当len=0或len=L时依然无法满足条件,直接跳过。
3.当l无妨满足题意,那之后的所有l都无法满足题意,也就是说长度相同则跳过
4.当然,标记数组是必不可少的
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
//count是当前组数,len是当前长度,group是目标组数,target是目标长度,last是当前索引,可以减少遍历时间
bool dfs(int count,int len,bool used[], int group, int target, int nums[], int last) {
if (count == group) return true;
if (len == target) return dfs(count + 1, 0, used, group, target,nums,0);//注意,这里last应该是0,因为上一组可能存在跳过元素的情况
int False = 0;
for (int i = last;i < n;i++) {
if (!used[i] && len + nums[i] <= target && nums[i] != False) {
used[i] = true;
//返回true的情况只有count=group,如果返回了true,说明这个情况是正确的,可以返回true
if (dfs(count, len + nums[i], used, group, target, nums,i+1)) return true;
used[i] = false;
False = nums[i];
if (len == 0 || len + nums[i] == target) {
//len=0不满足题意,说明最长的木棍无论怎么组合都无法满足题意,所以跳过
//len+nums[i]=target不满足题意(满足了的话会在上面返回true),和len=0类似,其实就是新一组的最长木棍不满足题意
return false;
}
}
}
return false;
}
int main() {
cin >> n;
int nums[70];
bool used[70];
memset(used, 0, sizeof(used));
int sum = 0;
for (int i = 0;i < n;i++) {
cin >> nums[i];
sum += nums[i];
}
sort(nums, nums+n, greater<int>());
int len = 0;
for (int l = nums[0];l <= sum;l++) {
if (sum % l != 0) continue;
int group = sum / l;
if (dfs(0, 0, used, group, l, nums,0)) {
cout << l;
return 0;
}
}
}
时间复杂度:算不来,鬼知道什么时候剪枝了
空间复杂度:O(n)
