深圳专门做网站的公司,电子商务网站推广目的分为,个人网站用wordpress吗,企业网络配置方案题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜#xff0c;每个瓜的重量为 Ai 。
小蓝刀功了得#xff0c;他可以把任何瓜劈成完全等重的两份#xff0c;不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好…题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜每个瓜的重量为 Ai 。
小蓝刀功了得他可以把任何瓜劈成完全等重的两份不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜请输出 −1 。
输入格式
输入的第一行包含两个整数 n, m用一个空格分隔分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai相邻整数之间使用一个空格分隔分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 10
1 3 13
样例输出
2
提示
对于 20% 的评测用例∑n≤10
对于 60% 的评测用例∑n≤20
对于所有评测用例1 ≤n≤301≤ Ai ≤ 10^9 1 ≤ m ≤ 10^9
思路
使用深度优先搜索解决, 对每个瓜的三种选择进行搜索, 解空间树是一颗完全三叉树, 时间复杂度为O(3^n), 肯定会超时, 故需要进行剪枝。
买半个瓜时需要将重量除2会产生小数故可以将重量数组都乘2最大重量也乘2。
搜索时需要记录三个状态当前层数pos当前总重量sum当前劈瓜的次数cnt以下情况需要剪枝 1当前劈瓜次数大于已求得的最小次数即cntans 2当前重量之和大于要求的重量即summ
但是这样仍然会超时还可以将重量数组降序排列使得更快剪枝。还可以创建一个重量数组的后缀数组suf这样在搜索时可以利用其剪枝若当前重量加上剩余的所有瓜重量之和小于要求的重量剪枝。
#includeiostream
#includealgorithm
#includecstring
using namespace std;
typedef long long ll;
const int N33;
double a[N];
double s[N];
bool st[N];
int n;
double m;
int cnt1e9;
//三种状态 整个 一半 不要
//dfs剪枝
//参数 当前层数 当前的西瓜的总重量 当前切了多少次
void dfs(int pos,double sum,int num)
{//当summ时 取最小的 返回上一层 if(summ){cntmin(cnt,num);return ;}//剪枝 sums[n]-s[pos-1] 是求当前sum加上之后所有的数均不能组成时 剪枝一下 if(summ||posn||cntnum||sums[n]-s[pos-1]m) return ;dfs(pos1,suma[pos],num);//整个要 dfs(pos1,sum(a[pos]/2),num1);//半个 dfs(pos1,sum,num);//都不要
}
//从大到小排 尽量减少切一半的次数
double cmp(double x,double y)
{return xy;}
int main()
{cinnm;for(int i1;in;i) {cina[i];}//排序 从大到小排 sort(a1,a1n,cmp);//求前缀和 for(int i1;in;i) s[i]s[i-1]a[i];dfs(1,0,0);if(cnt1e9) cout-1endl;else coutcntendl; return 0;
}
