做网站开发的有外快嘛,南宁网站搭建,石家庄新闻频道在线直播观看,河北省石家庄市裕华区题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜#xff0c;每个瓜的重量为 Ai 。
小蓝刀功了得#xff0c;他可以把任何瓜劈成完全等重的两份#xff0c;不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好…题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜每个瓜的重量为 Ai 。
小蓝刀功了得他可以把任何瓜劈成完全等重的两份不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜请输出 −1 。
思路
朴素做法
dfs每个瓜有三种选择
1.选瓜
2.劈瓜选瓜
3.不选瓜
则复杂度为3^n也就是3^30大概2e14绝对会超时。
所以需要剪枝优化
剪枝优化
1.如果当前已有重量所需重量则剪枝
2.如果当前已有重量剩下的重量总和所需重量剪枝求剩下的重量可以用后缀和数组优化
3.如果当前已经劈过的次数目前的劈瓜的最小次数剪枝
细枝末节
还有一些细枝末节可优化
1.除2的话可能会有小数但是浮点数运算会慢很多所以我们可以通过放大(乘2)原重量与所需重量。这样就可以只使用整型运算了。也可以用两个数组分别存储放大后的重量与相应的减半的数量这样可以在每次搜索时减少一次运算不过应该影响不大
2.将重量从大到小排序这样可以提前排除许多剪枝。
3.强制类型转换的耗时也不少。int转long之类的这一点是我没有想到的也是我卡题的原因经过不断不断一直一直反反复复的比对题解代码后才发现的。
大家可以感受一下
有转换的耗时结果超时一半多
#includebits/stdc.h
using namespace std;
int a[33];//原重
int b[33];//半重
long latter[33];
int m;
int n;
int ans100;
void dfs(int u,int sum,int k){//sum为int类型时long与int进行加减时会进行一次类型转换if(un||summ||kans||latter[u]summ){if(summ)ansmin(ans,k);return ;}dfs(u1,suma[u],k);dfs(u1,sumb[u],k1);dfs(u1,sum,k);
}
int main()
{cinnm;m*2;for(int i0;in;i){cinb[i];a[i]b[i]*2;}sort(a,an,greaterint());sort(b,bn,greaterint());for(int in-1;i0;i--)latter[i]latter[i1]a[i];dfs(0,0,0);if(ans!100)coutans;else cout-1;
} 没有类型转换的成功通过二者时间整整相差一倍
#includebits/stdc.h
using namespace std;
int a[33];//原重
int b[33];//半重
long latter[33];
int m;
int n;
int ans100;
void dfs(int u,long sum,int k){//sum为long类型时没有类型转换的耗时if(un||summ||kans||latter[u]summ){if(summ)ansmin(ans,k);return ;}dfs(u1,suma[u],k);dfs(u1,sumb[u],k1);dfs(u1,sum,k);
}
int main()
{cinnm;m*2;for(int i0;in;i){cinb[i];a[i]b[i]*2;}sort(a,an,greaterint());sort(b,bn,greaterint());for(int in-1;i0;i--)latter[i]latter[i1]a[i];dfs(0,0,0);if(ans!100)coutans;else cout-1;
} 也不排除是测评机的原因不过以后最好还是减少类似的类型转换更保险一些。
