北京开发网站wordpress沐风

北京开发网站,wordpress沐风,本地网站做淘宝客,番禺建设网站集团【题目描述】有n个函数#xff0c;分别为F1,F2,...,Fn。定义Fi(x)Aix2BixCi(x∈N∗)。给定这些Ai、Bi和Ci#xff0c;请求出所有函数的所有函数值中最小的m个#xff08;如有重复的要输出多个#xff09;。【输入】第一行输入两个正整数n和m。以下n行每行三个正整数#x…【题目描述】有n个函数分别为F1,F2,...,Fn。定义Fi(x)Aix2BixCi(x∈N∗)。给定这些Ai、Bi和Ci请求出所有函数的所有函数值中最小的m个如有重复的要输出多个。【输入】第一行输入两个正整数n和m。以下n行每行三个正整数其中第i行的三个数分别位Ai、Bi和Ci。输入数据保证Ai10Bi100Ci10000。【输出】将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行用空格隔开。【输入样例】3 10 4 5 3 3 4 5 1 7 1【输出样例】9 12 12 19 25 29 31 44 45 54【提示】【数据规模】n,m≤10000。1. 解题思路分析本题的核心目标是从 n 个二次函数生成的无数个值中筛选出最小的 m 个数。由于 m 远小于可能产生的数据总量直接计算所有值并排序O(N⋅Mlog(NM))显然不够高效。我们采用了“维护固定大小集合”的策略。数据结构选择大根堆虽然题目要求的是“最小”的数但在维护一个容量为 m 的候选集合时我们需要使用大根堆priority_queue默认大根堆。理由我们要时刻知道当前选出的 m 个数中最大的那个数是多少即堆顶元素。作用堆顶元素是当前候选集合的“门槛”。对于一个新计算出的函数值只有当它小于堆顶时它才有资格进入前 m 名。此时我们将堆顶弹出淘汰当前第 m 小将新值压入。关键优化利用函数单调性题目给定 A,B,C 均为正整数因此二次函数 f(x)A*x^2B*xC 在 x≥1 的区间上是单调递增的。 这一性质对于优化算法至关重要在遍历某一组参数 (A,B,C) 时我们让 x 从 1 开始递增。如果当前计算出的 f(x) 已经大于或等于堆顶元素由于函数的单调递增性后续的 f(x1),f(x2)... 必然也大于堆顶。结论此时无需继续计算该函数的后续值直接break跳出当前循环处理下一组函数。这一剪枝操作保证了算法不会超时。2. 算法流程总结初始化读取第一组函数参数计算前 m 个值推入优先队列建立初始的“最小m数”集合。动态更新依次读取后续 n−1 组函数参数。对于每组函数从 x1 开始计算。若 f(x)q.top()说明找到了更优解执行pop()和push(f(x))。若 f(x)≥q.top()触发单调性剪枝直接break。结果输出由于大根堆弹出顺序是从大到小需要将元素暂存入数组最后倒序输出以满足题目从小到大的要求。3. 实现细节与注意事项数据范围由于涉及到 x^2 的运算函数值可能会超过int范围因此优先队列和中间变量必须使用long long。输出数组类型代码中用于倒序输出的数组h应定义为long long以匹配优先队列的数据类型。时间复杂度在最坏情况下剪枝未频繁触发每次堆操作为 O(logm)。由于单调性的存在实际交换次数远小于理论上限整体效率足以通过测试点。//思路先通过第一组abc算出x1-m的m个f值存入优先队列最大堆后面每一组都通过与堆顶 //进行比较如果小于堆顶就存进去直到大于堆顶就开始下一组最后堆里存放的一定是最小的m个数输出即可 #include iostream #include queue using namespace std; int a,b,c; priority_queuelong long q;//最大堆 long long f(int x,int a,int b,int c){ return a*x*xb*xc; } int main(){ int n,m; cinnm; //第一组数据先存入优先队列 cinabc; for(int i1;im;i){ long long tmpf(i,a,b,c); q.push(tmp); } for(int i2;in;i){//从第二组开始比较 cinabc; for(int j1;jm;j){ long long tmpf(j,a,b,c); if(tmpq.top()){//tmp比堆里的最大值要小就弹出堆顶然后存入tmp q.pop(); q.push(tmp); } else{//i组当前j的情况下tmp已经大于堆顶即堆里的最大值就不需要让j继续增加了可以比较下一组了 break; } } } //因为要从小到大输出那就把堆先存进一个数组再输出 long long h[10001]; int cnt0;//存进多少个数 while(!q.empty()){ h[cnt]q.top(); q.pop(); } for(int icnt;i1;i--) couth[i] ; return 0; }