当前位置：首页 > news >正文

P1883 【模板】三分 | 函数

news 来源：原创 2025/8/28 12:45:55

题目描述

给定 n 个二次函数 f1(x),f2(x),…,fn(x)（均形如 ax2+bx+c），设 F(x)=max{f1(x),f2(x),...,fn(x)}，求 F(x) 在区间 [0,1000] 上的最小值。

输入格式

输入第一行为正整数 T，表示有 T 组数据。

每组数据第一行一个正整数 n，接着 n 行，每行 3 个整数 a,b,c，用来表示每个二次函数的 3 个系数，注意二次函数有可能退化成一次。

输出格式

每组数据输出一行，表示 F(x) 的在区间 [0,1000] 上的最小值。答案精确到小数点后四位，四舍五入。

说明/提示

对于 50% 的数据，n≤100。

对于 100% 的数据，T<10， n≤104，0≤a≤100，∣b∣≤5×103，∣c∣≤5×103。

#include <bits/stdc++.h>
using namespace std;const int MAXN = 100005;
int a[MAXN], b[MAXN], c[MAXN];
int n;double F(double x) {double res = -1e18;for (int i = 0; i < n; i++) {res = max(res, a[i]*x*x + b[i]*x + c[i]);}return res;
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i] >> b[i] >> c[i];}double l = 0.0, r = 1000.0;while (r - l > 1e-9) {  // 保证精度double lmid = l + (r - l) / 3;double rmid = r - (r - l) / 3;if (F(lmid) < F(rmid))r = rmid;elsel = lmid;}printf("%.4f\n", F(l));}return 0;
}

F(x) 表示：在每个 x 位置上，取所有函数中值最大的那一个

由于 a≥0，每个函数是凹的。它们的最大值组成的函数F(x)还是凹的

F(x) 先下降、后上升

三分法的思路是：

找出两个三分点 lmid, rmid
比较 F(lmid) 和 F(rmid)
因为 F(x) 是凹函数（先降后升），
- 如果 F(lmid) < F(rmid)，说明最小值在左侧
- 否则在右侧
不断缩小区间 l 到 r

直到区间极小（小于 10^-9），我们认为找到了极小值点。

由于浮点数存在精度问题，当进行多次计算时，会有非常微小的误差。如果使用 l <= r，在接近正确解的时候，l 和 r 可能永远不完全相等，所以会陷入死循环。

精度终止条件：使用 r - l > epsilon（比如 1e-9）可以确保在精度范围内停止，不依赖于 l 和 r 是否恰好相等。只要它们之间的差距小到几乎无法再缩小，就认为已经找到了最优解

P1883 【模板】三分 | 函数

题目描述给定 n 个二次函数 f1(x),f2(x),…,fn(x)（均形如 ax2bxc），设 F(x)max{f1(x),f2(x),...,fn(x)}，求 F(x) 在区间 [0,1000] 上的最小值。输入格式输入第一行为正整数 T，表示有 T 组数据。每组…...

编程日记 2025/8/28 12:45:55

Ruoyi-vue plus 5.2.2 flowble设计流程点击开始流程图错误

网关设置条件或者是事件删除后出现，点击网关节点无法找到下面的事件节点。配置页面事件错误，点背景配置进去了事件，发现再次加载，或者删除的时候VUE页面无法加载。解决方式：查看XML文件，这个节点是否存在…...

编程日记 2025/8/28 12:44:39

MySQL学习笔记（三）——图形化界面工具DataGrip

目录 1. 图形化界面工具 2.下载 3. 安装 3.1 安装步骤 3.2 激活说明 4. 使用 4.1 汉化教程 4.2 使用 1. 图形化界面工具上述，我们已经讲解了通过 DDL 语句，如何操作数据库、操作表、操作表中的字段，而通过 DDL 语句执行在命令进行操…...

编程日记 2025/8/27 21:21:19

keil软件仿真

设置选择软件仿真。修改参数。获取参数找到自己的芯片信号。这里用的是F103ZET6 复制下来，并对其进行修改。接下来进入仿真即可...

编程日记 2025/8/17 22:34:40

每日一题（小白）模拟娱乐篇14

直接理解题意，一分钟扩散一次，那么2020分钟也就是需要循环2020次，然后加入扩散后的条件，每一个次扩散使方格子的总量1（只要有一个点扩散就无需看其他的点），若干次循环过后总数之和即所有黑色格子…...

编程日记 2025/8/23 1:52:13

（二）使用Android Studio开发基于Java+xml的安卓app之环境搭建

以下是使用Android Studio搭建基于Java和XML的Android应用开发环境的详细步骤： 一、系统要求操作系统：Windows 7/8/10/11（64位）内存：建议8GB及以上磁盘空间：至少5GB空闲（建议预留10GB以上&…...

编程日记 2025/8/28 12:42:04

STM32定时器通道1-4（CH1-CH4）的引脚映射关系

以下是 STM32定时器通道1-4（CH1-CH4）的引脚映射关系的详细说明，以常见型号为例。由于不同系列/型号差异较大，请务必结合具体芯片的参考手册确认。一、STM32F1系列（如STM32F103C8T6） 1. TIM1（高级定时器）通道默认引脚重映射引脚（部分/完全）备注CH1PA8无互补输出CH1…...

编程日记 2025/8/17 18:48:18

看爬山虎学本领软爬机器人来创新各种场景能适应

*本文只做阅读笔记分享* 一、灵感来源：向植物取经大家好！今天来聊一款超酷的软爬机器人，它的灵感来自会攀爬的植物——爬山虎。大家都知道，爬墙高手爬山虎能在各种复杂墙面轻松生长攀爬，可现有的攀爬机器人在复杂…...

编程日记 2025/8/23 2:06:58

Spring AI Alibaba示例项目深度解析：dashscope-audio子模块详解

Spring AI Alibaba示例项目深度解析：dashscope-audio子模块详解一、模块定位与核心价值 1.1 功能定位 • 音频处理核心组件：基于阿里云DashScope平台实现STT（语音识别）和TTS（文生语音）双模态能力 • 企业级解决方案：提供同步/异步/流式三种调用范式，适配不同业务场景…...

编程日记 2025/8/22 11:19:26

Linux 下日志系统搭建全攻略

目录一、引言二、日志系统基础日志级别日志输出格式三、创建日志所需函数认识可变参数编辑获取时间的函数小结四、创建日志一、引言在 Linux 环境中开发 C/C 程序时，日志系统是不可或缺的一部分。它不仅有助于调试程序、排查问题&#xff…...

编程日记 2025/8/28 1:38:12

前端布局难题：父元素padding导致子元素无法全屏？3种解决方案

大家好，我是一诺。今天要跟大家分享一个我在实际项目中经常用到的CSS技巧——如何让子元素突破父元素的padding限制，实现真正的全屏宽度效果。为什么会有这个需求？ 记得我刚入行的时候，接到一个需求：要在内容区插入…...

编程日记 2025/8/28 12:42:04

写.NET可以指定运行SUB MAIN吗?调用任意一个里面的类时,如何先执行某段初始化代码?

VB.NET 写.NET可以指定运行SUB MAIN吗?调用任意一个里面的类时,如何先执行某段初始化代码? 分享 1. 在 VB.NET 中指定运行 Sub Main 在 VB.NET 里，你能够指定 Sub Main 作为程序的入口点。下面为你介绍两种实现方式： 方式一：在项目属性…...

编程日记 2025/8/27 1:06:04

long int Freq; unsigned int Timer_1000Ms; 加上 TMOD | 0x05; void Timer0Init(void) //0毫秒12.000MHz {AUXR & 0x7F; //定时器时钟12T模式TMOD & 0xF0; //设置定时器模式TMOD | 0x05;TL0 0x00; //设置定时初值TH0 0x00; //设置定时初值TF0 0; //清除TF0标…...

编程日记 2025/8/25 12:17:08

word导出PDF老是目录格式变化的问题

这里是写给和我一样的笨蛋的经验帖，适合试了很多网上的经验，结果都用不成的傻瓜蛋，先说好，我是傻瓜蛋，我不是在攻击谁，我们只是客观的，缺根弦罢了。这些帖子里讲的最多的应该是：“…...

编程日记 2025/8/22 18:18:58

P1577 切绳子(二分）

题目描述有 N 条绳子，它们的长度分别为 Li。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？答案保留到小数点后 2 位(直接舍掉 2 位后的小数)。输入格式第一行两个整数 N 和 K，接下来 N 行&#xf…...

编程日记 2025/8/25 9:01:40

高级：分布式系统面试题精讲

一、引言分布式系统在现代软件开发中占据重要地位，其设计和实现需要考虑多个关键因素。面试官通过相关问题，考察候选人对分布式系统核心概念的理解、实际应用能力以及在复杂场景下的问题解决能力。本文将深入分析分布式系统的CAP定理、一致性协议、分布…...

编程日记 2025/8/23 16:07:52

【速写】SFT案例实操（以Qwen2.5-instruct-0.5B）

参考资料： https://openbayes.com/console/bbruceyuan/containers/OPg9Oo99ET6https://www.bilibili.com/video/BV1NM1tY3Eu5 LoRA微调案例首先还是要安装： !pip install -q accelerate peft bitsandbytes transformers sentencepiece !pip install…...

编程日记 2025/8/24 4:16:51

springboot457-库存管理系统(源码+数据库+纯前后端分离+部署讲解等)

💕💕作者： 爱笑学姐 💕💕个人简介：十年Java，Python美女程序员一枚，精通计算机专业前后端各类框架。 💕💕各类成品Java毕设。javaweb，ssm&#xf…...

编程日记 2025/8/26 20:05:16

Node.js中间件的分类

目录 Node.js 中间件的分类与详细介绍 1. 目录结构 2. Express 中间件的主要分类 3. 代码实现 1. 应用级中间件（作用于整个应用） 示例：日志记录中间件 2. 路由级中间件（仅作用于特定路由） 示例：身份…...

编程日记 2025/8/25 15:02:53

棒球规则快速入门·棒球1号位

棒球规则快速入门： 得分方式进攻方击球后，依次跑过一、二、三垒并返回本垒得1分。若击球直接飞出外场围栏（全垒打），击球员和已上垒的跑垒员均可得分。比赛结构共9局，每局分上下半场，双方各…...

编程日记 2025/8/25 17:40:25

【深度学习】通过colab将本地的数据集上传到drive

本地数据集上传到colab很慢，而且断开后就没了，因此通过colab将本地的数据集上传到drive，即使断开连接，第二次连接后挂载drive后即可直接使用数据集。步骤一、将本地数据集上传到colab的临时文件夹中，由于将文件夹上传…...

编程日记 2025/8/25 19:44:59

MYSQL 存储引擎和日志

存储引擎 InnoDB 支持行级别的锁粒度，MyISAM 不支持，只支持表级别的锁粒度。MyISAM 不提供事务支持。InnoDB 提供事务支持，实现了 SQL 标准定义了四个隔离级别。MyISAM 不支持外键，而 InnoDB 支持。MyISAM 不支持 MVCC&#xff0c…...

编程日记 2025/8/25 6:52:23

【2022】【论文笔记】太赫兹量子阱——

前言类型太赫兹 + 量子阱太赫兹 + 量子阱太赫兹+量子阱期刊红外与毫米波学报红外与毫米波学报红外与毫米波学报作者张真真 ,...

编程日记 2025/8/23 23:43:14

【NLP 面经 7、常见transformer面试题】

目录 1. 为何使用多头注意力机制？ 2. Q和K使用不同权重矩阵的原因 3. 选择点乘而非加法的原因 4. Attention进行scaled的原因 5. 对padding做mask操作 6. 多头注意力降维原因 7. Transformer Encoder模块简介 8. 乘以embedding size的开方的意义 9. 位置编码 10. 其…...

编程日记 2025/8/17 22:31:31

在js中数组相关用法讲解

数组 uniqueArray 简单数组去重 /*** 简单数组去重* param arr* returns*/ export const uniqueArray <T>(arr: T[]) > [...new Set(arr)];const arr1 [1,1,1,1 2, 3];uniqueArray(arr); // [1,2,3]uniqueArrayByKey 根据 key 数组去重 /*** 根据key数组去重* …...

编程日记 2025/8/25 6:51:36

第四章 react-redux，@reduxjs/toolkit依赖，学习

redux系列文章目录第一章简单学习redux,单个reducer 第二章简单学习redux,多个reducer 第三章 redux和react-redux，reduxjs/toolkit依赖结合使用第五章两张图告诉你redux常使用的api有哪些前言本章将使用react-redux，reduxjs/toolkit依赖创…...

编程日记 2025/8/28 11:27:11

雅思7分听说读写专项书籍推荐

对于目标 7分以上的雅思考生（中高级水平），选对资料真的事半功倍。下面按照听力、阅读、写作、口语、综合书籍五大类来分别列举高分推荐书籍，每本书包括：适合人群、核心内容、推荐理由，并贴合7分目标。 …...

编程日记 2025/8/27 6:14:15

C++容器使用说明

C标准库提供了多种容器，分为序列容器、关联容器、无序关联容器、容器适配器及其他相关类型。以下是所有标准容器的分类及简要说明： 1. 序列容器（Sequence Containers） 按线性顺序存储元素，支持随机或顺序访问。 vecto…...

编程日记 2025/8/24 16:16:43

Python-函数

1. 函数基础 1.1 定义函数在Python中，使用def关键字来定义函数： def greet():"""简单的问候函数"""print("Hello, World!")1.2 调用函数定义函数后，可以通过函数名加括号来调用： …...

编程日记 2025/8/23 11:12:23

【Redis】数据的淘汰策略

目录淘汰策略方案（8种） LRU和LFU策略的区别使用建议手搓LRU算法方式一方式二大家好，我是jstart千语。今天和大家回来聊一下redis，这次要讲的是它的淘汰策略。为什么需要淘汰策略呢，就是当redis里面的内存占…...

编程日记 2025/8/23 12:18:24

第七章：从类库到服务的分布式基石_《凤凰架构：构建可靠的大型分布式系统》

第七章：从类库到服务的分布式基石一、服务发现（Service Discovery） 核心目标：解决分布式系统中服务实例动态变化时如何定位可用服务的问题。 1. 服务发现的意义动态环境挑战： 微服务架构中，服务实例的…...

编程日记 2025/8/25 12:02:38

spring-ai-alibaba第九章使用Milvus构建大模型RAG应用

1、pom文件 <dependencies><dependency><groupId>com.alibaba.cloud.ai</groupId><artifactId>spring-ai-alibaba-starter</artifactId><version>${spring-ai-alibaba.version}</version></dependency><dependency&g…...

编程日记 2025/8/24 19:50:30

手撕LLM（一）：从源码出发，探索LLM推理全流程

2025年，大模型爆发元年，各种各样的大模型、框架、工具层出不穷，不断刷新人们应用大模型的门槛，短短10行代码，就能完成“加载模型加载数据集推理强化学习”的全流程训练，但其底层的运行机制也被高度抽象的接…...

编程日记 2025/8/26 10:21:47

讯飞语音听写（流式版）开发指南

语音交互大模型的功能越来越受到重视。讯飞语音听写（流式版）为开发者提供了一种高效、准确的语音识别解决方案。本文将基于 Home.vue、iat_xfyun.js 和 sparkChat.js 这三个文档，详细阐述讯飞语音听写（流式版）的开发逻…...

编程日记 2025/8/28 12:45:47

P3654 First Step (ファーストステップ)

题目描述可是……这个篮球场，好像很久没有使用过的样子啊…… 里面堆满了学校的各种杂物呢…… 我们 Aqours 的成员要怎么在里面列队站下呢？ 我们浦之星女子学院的篮球场是一个 R 行 C 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)&a…...

编程日记 2025/8/26 11:13:20

MySQL篇（六）MySQL 分库分表：应对数据增长挑战的有效策略

MySQL篇（六）MySQL 分库分表：应对数据增长挑战的有效策略 MySQL篇（六）MySQL 分库分表：应对数据增长挑战的有效策略一、引言二、为什么需要分库分表2.1 性能瓶颈2.2 存储瓶颈2.3 高并发压力三、分库分表的方…...

编程日记 2025/8/28 9:37:54

SonarQube 配置SQL Server 数据库遇到的问题

之前本机跑了一套SonarQube的社区版，默认使用的是H2数据库，那么我把它练到我机器上的SQL Server数据库了，期间遇到以下两个问题，并在配置过程中解决掉，特将这个过程记录下来。一、JDBC连接SQL Server问题 1. 问题出…...

编程日记 2025/8/27 1:26:28

23种设计模式-行为型模式-备忘录

文章目录简介问题解决代码关键实现要点功能扩展方向总结简介备忘录是一种行为设计模式， 允许在不暴露对象实现细节的情况下保存和恢复对象之前的状态。问题假如你正在开发一款文字编辑器应用。你想加入撤销功能。你可以采用直接的方式来实现: 程序在执行任…...

编程日记 2025/8/22 14:47:24

IDEA/WebStrom操作之commit前批量清除console.log()与debugger

前言： 在前端开发过程中，往往需要频繁用到console.log()与debugger，来观察数据具体情况以及断点调试。在经历了水生火热的开发动作后，往往会残留一地console.log()和debugger，若开发者还得手动在多个文件中一个个去除…...

编程日记 2025/8/26 17:26:17

每日算法-250405

34. 在排序数组中查找元素的第一个和最后一个位置题目思路本题的核心思路是二分查找。解题过程问题分析：在一个升序排列的数组中查找一个目标值 target 的起始和结束位置。这是一个典型的二分查找应用场景。核心转换：题目要求找到 target 的第一个…...

编程日记 2025/8/26 5:13:18

设计模式简述（四）模板方法模式

模板方法模式描述基本定义使用描述当一系列业务的基本流程是相同的，对于不同的业务可以在各自子类实现所谓模板方法指的就是父类中固定的那部分代码其实这里的思想和前面设计原则中开闭原则的描述是一致的，父类中的模板代码就是稳定的部分&#x…...

编程日记 2025/8/23 19:38:31

论文修改时有哪些需要注意的问题？

论文修改是学术写作中不可或缺的环节，直接影响成果的专业性和说服力。许多作者因忽略细节或急于定稿，导致论文质量大打折扣。那么，如何修改才能提升论文的严谨性与可读性呢？ 一、逻辑结构论文修改时，先从头到尾通读…...

编程日记 2025/8/27 21:36:12

JAVA阻塞队列

目录一、什么是阻塞队列？特点是什么？ 二、阻塞队列的两种创建方式： 1、使用 ArrayBlockingQueue<>( ) : 2、使用 LinkedBlockingQueue<>( ) ： 三、阻塞队列方法的使用： 阻塞队列关键的两个方法&…...

编程日记 2025/8/27 1:26:30

tomcat与spring-web

文章目录 SpringServletContainerInitializerWebApplicationInitializerWebApplicationInitializer接口AbstractContextLoaderInitializer抽象类AbstractDispatcherServletInitializer抽象类AbstractAnnotationConfigDispatcherServletInitializer抽象类 WebApplicationContext…...

编程日记 2025/8/23 4:28:45

将电脑控制手机编写为MCP server

文章目录电脑控制手机后，截屏代码复习MCP server构建修改MCP的config文件测试效果困惑电脑控制手机后，截屏代码复习 def capture_window(hwnd: int, filename: str = None) -> dict:""&...

编程日记 2025/8/18 0:59:35

[ctfshow web入门]burpsuite的下载与使用

下载吾爱破解网站工具区下载burpsuite https://www.52pojie.cn/thread-1544866-1-1.html 本博客仅转载下载链接，下载后请按照说明进行学习使用打开配置 burpsuite配置 burpsuite代理设置添加127.0.0.1:8080 浏览器配置如果是谷歌浏览器，打开win…...

编程日记 2025/8/17 22:31:49

文章记单词 | 第25篇（六级）

一，单词释义 mathematical：形容词，意为 “数学的；数学上的；运算能力强的；关于数学的”trigger：名词，意为 “（枪的）扳机；（炸弹的&…...

编程日记 2025/8/22 1:28:51

讯飞语音合成(流式版)语音专业版高质量的分析

一、引言在现代的 Web 应用开发中，语音合成技术为用户提供了更加便捷和人性化的交互体验。讯飞语音合成（流式版）以其高效、稳定的性能，成为了众多开发者的首选。本文将详细介绍在 Home.vue 文件中实现讯飞语音合成（流…...

编程日记 2025/8/28 1:12:43

【MediaPlayer】基于libvlc+awtk的媒体播放器

基于libvlcawtk的媒体播放器 libvlc下载地址 awtk下载地址代码实现libvlc相关逻辑接口UI媒体接口实例化媒体播放器注意事项 libvlc 下载地址可以到https://download.videolan.org/pub/videolan/vlc/去下载一个vlc版本，下载后其实是vlc的windows客户端&#xff0…...

编程日记 2025/8/26 11:28:52

复古未来主义屏幕辉光像素化显示器反乌托邦效果PS(PSD)设计模板样机 Analog Retro-Futuristic Monitor Effect

这款模拟复古未来主义显示器效果直接取材于 90 年代赛博朋克电影中的黑客巢穴，将粗糙的屏幕辉光和像素化的魅力强势回归。它精准地模仿了老式阴极射线管显示器，能将任何图像变成故障频出的监控画面或高风险的指挥中心用户界面。和……在一起 2 个完全可编…...

编程日记 2025/8/22 9:36:06

题目描述

输入格式

输出格式

说明/提示

相关文章：