网站系统建设招标公告,手机做网页的软件叫什么,知名企业排名,东莞网站建设备案折半搜索 知识点折半搜索的原理折半搜索的过程 例题题目#xff1a;世界冰球锦标赛题目描述输入样例输出样例提示 世界冰球锦标赛题解思路代码 知识点
折半搜索的原理 折半搜索是一种技巧#xff0c;实际上就是将一个次搜索过程分成两次进行#xff0c;然后将两次搜索的结果… 折半搜索 知识点折半搜索的原理折半搜索的过程 例题题目世界冰球锦标赛题目描述输入样例输出样例提示 世界冰球锦标赛题解思路代码 知识点
折半搜索的原理 折半搜索是一种技巧实际上就是将一个次搜索过程分成两次进行然后将两次搜索的结果合并这种操作能大大减少用时。 如有n个东西问有多少种选取方案分别选了哪几个?暴力时间复杂度 O ( 2 n ) O(2^n) O(2n)折半后时间复杂度 O ( 2 n 2 × 2 ) O(2^{\frac{n}{2}}\times2) O(22n×2) 折半搜索的过程 先将要搜索的部分分成两部分然后进行第一部分的搜索将结果存起来再将需要做的操作做完最后进行第二次搜索将结果直接与第一次的匹配统计答案并输出。 例题
题目世界冰球锦标赛
时间限制1秒 内存限制128M
题目描述 从N个数中选出一些数使其的和不超过M输出有多少种选取方案。 ( 1 ≤ N ≤ 40 , 1 ≤ M ≤ 1 0 18 ) (1≤N≤40,1≤M≤10^{18}) (1≤N≤40,1≤M≤1018) 输入样例
5 1000
100 1500 500 500 1000输出样例
8提示 八种方案分别是 · 一场都不看溜了溜了 · 价格 100 的比赛 · 第一场价格 500 的比赛 · 第二场价格 500 的比赛 · 价格 100 的比赛和第一场价格 500 的比赛 · 价格 100 的比赛和第二场价格 500 的比赛 · 两场价格 500 的比赛 · 价格 1000 的比赛 世界冰球锦标赛题解
思路 把比赛平均分成两份进行完第一次搜索后将结果排个序因为合并时要用到二分查找然后进行第二次搜索搜出一个答案用二分查找出最大是哪个匹配方式累加它的编号因为排了序最后输出答案。 代码
#include algorithm
#include cstdio
#include iostream
#include string
using namespace std;
long long a[50],n,m;
long long cnt0,anss[1500000],ans0;
void dfs(long long x,long long sum,long long end,int flag){if(summ){return ;}if(xend1){coutsumendl; if(flag0){anss[cnt]sum; }else{ansupper_bound(anss1,anss1cnt,m-sum)-anss-1;}return ;}dfs(x1,suma[x],end,flag);dfs(x1,sum,end,flag);
}
int main() {scanf(%lld %lld,n,m);for(int i1;in;i){scanf(%lld,a[i]);}dfs(1,0,n/2,0);sort(anss1,ansscnt1);dfs(n/21,0,n,1);printf(%lld,ans);return 0;
}
