首页 > 其他分享 >洛谷题单指南-二叉堆与树状数组-P2085 最小函数值

洛谷题单指南-二叉堆与树状数组-P2085 最小函数值

时间:2024-11-11 15:45:44浏览次数:5  
标签:node return idx val int 洛谷题 二叉 P2085 函数

原题链接:https://www.luogu.com.cn/problem/P2085

题意解读:有n个函数,函数中x取值>=1,计算所有函数能得到的值中最小的m个。

解题思路:

函数中x取值是>=1的整数,因此每个函数的值是f(1),f(2),f(3)....,是一个递增序列,题目本质上是要从n个递增序列中找到前m个最小的数。

首先,对所有函数计算f(1),放入优先队列,最小值一定在其中。

第二小的值如何计算?可以将最小的f(1)弹出,计算相应的f(2),再放回优先队列,再取此时最小值,即可得到第二小的值。

第三、四。。。m小的值计算方法以此类推。

用算法的语言描述:

1、初始计算所有函数在x=1时的值

2、取最小值

3、然后将最小值对应的函数x+1再计算函数值

4、重复2,直到取m次最小值

由于优先队列要记录函数值,取得函数值时x的值,以及第几个函数,因此可以定义结构体

struct Node
{
    int val, idx, x; //val函数值,idx函数编号,x未知数取值
    bool operator < (const Node &node) const &
    {
        if(val != node.val) return val > node.val;
        if(x != node.x) return x > node.x;
        return idx > node.idx;
    }
};

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

struct Node
{
    int val, idx, x; //val函数值,idx函数编号,x未知数取值
    bool operator < (const Node &node) const &
    {
        if(val != node.val) return val > node.val;
        if(x != node.x) return x > node.x;
        return idx > node.idx;
    }
};

int n, m;
int a[N], b[N], c[N];
priority_queue<Node> q;

int f(int idx, int x)
{
    return a[idx] * x * x + b[idx] * x + c[idx];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i] >> b[i] >> c[i];
        q.push({f(i, 1), i, 1});
    }
    while(m--)
    {
        Node p = q.top(); q.pop();
        cout << p.val << " ";
        q.push({f(p.idx, p.x + 1), p.idx, p.x + 1});
    }
    return 0;
}

 

标签:node,return,idx,val,int,洛谷题,二叉,P2085,函数
From: https://www.cnblogs.com/jcwy/p/18539897

相关文章

  • 96. 不同的二叉搜索树
    题目链接解题思路暴力怎么做?n个节点,我们要先选头节点i,头节点选中之后,左子树的节点数就决定了,右子树的节点数也就决定了,所以选择头节点i后,不同的数目是左子树不同数目*右子树不同数目,这又是子问题了,又可以递归得到结果。有一个细节,假设n等于5,1,2,3,4,5,假设现在选择了3为头......
  • leetcode1008. 前序遍历构造二叉搜索树
    给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。二叉搜索树 是一棵二叉树,其中每个节点, Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值......
  • 代码随想录——二叉树-12.平衡二叉树
    自顶向下递归(前序遍历)这种方法是一开始想到的,虽然ac了但是对于它的本质却不清不楚,不知道时间复杂度,不知道属于前序遍历。思路首先得到root节点的左右子树的深度(左右),若深度差绝对值大于1(中),则root为根的树不是平衡二叉树;否则继续递归root的左右子树,其左右子树都是平衡二叉树......
  • 代码随想录——二叉树-11.完全二叉树的节点个数
    思路一、层序遍历,时间复杂度O(n)二、利用完全二叉树性质,时间复杂度O(logn*logn)(小于O(n))完全二叉树性质:若树深度为h,则前h-1层节点都达到最大值。第h层节点都集中在最左侧的位置完全二叉树要么1.是满二叉树2.最后一层没满满二叉树计算节点数太方便了,直接用公式2^h-1。......
  • 数据结构 ——— 链式二叉树oj题:对称二叉树
    目录题目要求手搓一个对称二叉树代码实现 题目要求给你一个二叉树的根节点 root ,检查它是否轴对称手搓一个对称二叉树代码演示://数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{ BTDataTypedata;//每个节点的数据......
  • 实现链式结构二叉树
    目录需要实现的操作链式结构二叉树实现结点的创建前序遍历中序遍历后序遍历计算结点个数计算二叉树的叶子结点个数 计算二叉树第k层结点个数计算二叉树的深度查找值为x的结点 销毁层序遍历判断是否为完全二叉树 总结需要实现的操作//前序遍历voidPreOr......
  • 每日一题之二叉树
    已知结点元素值为正整数且值不相同的一棵二叉树。该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。输入一个整数x,针对此二叉树编写程序求出x的右子树中所有结点值的和(若x不在树上,输出-1)。 输入说明:第一行输入某二叉树的先序遍历序列第二行输入该二叉树的中序遍历......
  • 洛谷题单入门1顺序结构(C语言版)
    【入门1】顺序结构Hello,World!#include<stdio.h>intmain(){printf("Hello,World!");return0;}输出字符菱形#include<stdio.h>intmain(){printf("*\n");printf("***\n");printf("*****\n&q......
  • 代码随想录算法训练营第19天|235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插入
    235.二叉搜索树的最近公共祖先文章链接:https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/思路:利用二叉搜索树的特性,当第一次遇到在[p,q]区间或[q,p]区间的元素的节点,则......
  • 根据二叉树创建字符串
    题目:606.根据二叉树创建字符串-力扣(LeetCode)给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空......