深圳网站建设联系电话,重庆市建设工程施工安全管理网官网,wordpress还是hexo,有哪些调查网站可以做兼职题目传送门
前言
说实话这题根本用不到什么折半……#xff0c;今天看机房大佬写了半天加了一堆剪枝还以为很难#xff0c;其实是你们想复杂了
20分钟不到从看题到代码实现
这题其实只需要可行性剪枝加排序 哦还有个后缀和
进入正题
小木棍子都听说过吧 没错就是小波上…题目传送门
前言
说实话这题根本用不到什么折半……今天看机房大佬写了半天加了一堆剪枝还以为很难其实是你们想复杂了
20分钟不到从看题到代码实现
这题其实只需要可行性剪枝加排序 哦还有个后缀和
进入正题
小木棍子都听说过吧 没错就是小波上课打挂那道
跟这题没多大关系不过如果你切了小木棍就会觉得这道题很简单
讲讲我一开始的思路
一开始因为机房大佬在各种卡常玄学剪枝大叫折半是个好东西还以为是个和小木棍一样的毒瘤
讲真我不喜欢打折半
第一眼看排序然后和埃及分数一样根据后续的瓜全买能不能满足剪枝然后搜索的时候加个二分寻找当前第一个切开比剩下小的值
后面发现因为数据水所以加不加二分没差多少
最后清晰的讲述一下我的思路
第一步先将所有的元素从大到小进行排序然后做一下后缀和后面可行性剪枝用
第二步开始搜索。
搜索的时候注意顺序要从前往后搜也就是说后面被搜到的元素不能大于前面的这里感性理解一下如果大的搜了搜小的然后搜完小的又去搜大的就重复了排序就没有意义了
关于可行性剪枝自然就是用第一步求出的后缀和直接判断一下后面所有的瓜加起来有没有剩下需要的瓜多
然后就结束了
关于一些小技巧
可以在读入的时候就把数据乘 2 这样就可以用 l o n g l o n g long long longlong 存下了机房大佬说double常数很大
然后就是把题目看清楚求的是 需要切开的瓜还有如果不行要输出 − 1 -1 −1 不然你会因此 W A WA WA 一个点
Code
#include bits/stdc.h
#define int long long//记得开 long long
#define ull unsigned long longconst int N 1e610;
const int M 1e410;
const int mod 1e97;
const int INF 0x3f3f3f3f;using namespace std;
int a[40],n,m,b[40];
bool esmite(int pos,int res){return b[pos1] res;
}
int ans INF;
int find(int x){// STL熟练的可以使用 upper_bound 或者 lower_bound 本蒟蒻这两玩意用法分不清故手写 int l 1, r n;while(l r){int mid (lr) 1;if(a[mid] / 2 x){r mid;}else{l mid1;}}return l;
}
void dfs(int num,int rest,int pos){//num 当前切开了几个瓜rest 还剩下需要多少瓜pos当前搜到哪个位置了防止往前搜 if(rest 0){//统计答案 ans min(ans,num);return;}if(!esmite(pos,rest)) return;//可行性剪枝 for(int i max(pos1,find(rest));i n; i){//当然这里也可以直接pos1说过了数据水 if(a[i] / 2 rest) continue;dfs(num1,rest - a[i] / 2, i);if(a[i] rest) continue;dfs(num,rest - a[i], i);}
}
signed main(){cin n m;m *2;//乘2小技巧 for(int i 1; i n; i){cin a[i];a[i] * 2;}sort(a1,a1n,greaterint());//排序 for(int i n; i 0; i--){//后缀和 b[i] b[i1] a[i];}dfs(0,m,0);if(ans INF) cout -1;else cout ans;return 0;
}
后记
瓜瓜永远的神 吃瓜教万岁
