Codeforces Round 973 (Div. 2) - D题
传送门:Problem - D - Codeforces
题目大意:

思路:
尽量要 最大值变小,最小值变大
即求 最大值的最小 和 最小值的最大 -> 二分答案
AC代码:
代码有注释
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];auto check1 = [&](int limit){// limit 此时就是 最大值的最小值// 经过操作后,若 b[i] <= limit 就是ok的,否则就放弃这个值// 最大值最小for (int i = 1; i <= n; i++) b[i] = a[i];for (int i = 1; i < n; i++){// b[i] 超过 limit ,就要减小 b[i]if (b[i] > limit){b[i + 1] += (b[i] - limit);b[i] = limit;}}for (int i = 1; i <= n; i++){if (b[i] > limit) return false;}return true;};int left = 0; int right = 1e12;while (right > left){int mid = left + right >> 1;if (check1(mid))right = mid;else left = mid + 1;}int ans = left;auto check2 = [&](int limit){// 最小值最大// limit 就是最小值的最大值for (int i = 1; i <= n; i++) b[i] = a[i];for (int i = 1; i < n; i++){if (b[i] > limit){b[i + 1] += (b[i] - limit);b[i] = limit;}}int mn = 2e18;for (int i = 1; i <= n; i++) mn = min(mn, b[i]);// 经过操作后,mn 仍大于 limit ,则可以继续增大limitif (mn >= limit)return true;else return false;};left = 0; right = 1e12;while (right > left){int mid = left + right + 1 >> 1;if (check2(mid))left = mid;else right = mid - 1;}cout << ans - left << endl;
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}
加练二分:
传送门:Problem - D - Codeforces
题目大意:


思路:
二分 顶点1要加上的值
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx;
int a[N];
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool dfs(int u, int limit)
{if( limit > 1e9 ) return false; // 一定要加这个代码,否则就会爆 long long// 所有顶点的值都是 <= 1e9 的,所以 limit 肯定不能大于 1e9if (a[u] < limit){int temp = limit - a[u];limit += temp;}bool flag = false;for (int i = h[u]; i != -1; i = ne[i]){flag = true;int j = e[i];if (!dfs(j, limit)) return false;}if (!flag){if (a[u] >= limit) return true;else return false;}else return true;
}
bool check(int limit)
{for (int i = h[1]; i != -1; i = ne[i]){int j = e[i];if (!dfs(j, limit)) return false;}return true;
}
void solve()
{memset(h, -1, sizeof h); idx = 0;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 2; i <= n; i++){int fa; cin >> fa;add(fa, i);}int left = 0; int right = 1e9;while (right > left){int mid = left + right + 1 >> 1;if (check(mid)) left = mid;else right = mid - 1;}cout << a[1] + left << endl;
}
signed main()
{int tt; cin>> tt;while(tt--)solve();return 0;
}
相关文章:
Codeforces Round 973 (Div. 2) - D题
传送门:Problem - D - Codeforces 题目大意: 思路: 尽量要 最大值变小,最小值变大 即求 最大值的最小 和 最小值的最大 -> 二分答案 AC代码: 代码有注释 #include<bits/stdc.h> using namespace std; #…...
threejs性能优化之gltf文件压缩threejs性能优化之glb文件压缩
在使用Three.js进行3D图形开发时,GLTF(GL Transmission Format)文件因其高效性和灵活性而广受欢迎。然而,随着模型复杂度的增加,GLTF文件的大小也会显著增加,这可能会对加载时间和渲染性能产生负面影响。为…...
设计模式 享元模式(Flyweight Pattern)
享元模式 简绍 享元模式(Flyweight Pattern)是一种结构型设计模式,它的目的是通过共享技术来有效地支持大量细粒度的对象。享元模式可以极大地减少内存的使用,从而提高程序的性能。它特别适用于需要创建大量相似对象的场景&#…...
Leetcode 3290. Maximum Multiplication Score
Leetcode 3290. Maximum Multiplication Score 1. 解题思路2. 代码实现 题目链接:3290. Maximum Multiplication Score 1. 解题思路 这一题的话就是一个比较暴力的动态规划,这里就不过多展开了,参考代码看一下就行。 2. 代码实现 给出py…...
CefSharp_Vue交互(Element UI)_WinFormWeb应用(3)---通过页面锁屏和关机(含示例代码)
一、预览 实现功能:通过vue标题栏按钮锁屏和关机 1.1 预览 1.2 代码 锁屏代码csharp LockWorkStation() 关机代码chsharp 注意vue代码参数和此参数一致(0/1/2) 方法ExitWindowsEx()...
unity UnityWebRequest 的request.downloadHandler 空应用
unity UnityWebRequest 的request.downloadHandler 空应用 private IEnumerator Test_Get() {UnityWebRequest request new UnityWebRequest(tmp_getURL, "GET");yield return request.SendWebRequest();if (request.result UnityWebRequest.Result.ConnectionErr…...
使用 UWA Gears 定位游戏内存问题
UWA Gears 是UWA最新发布的无SDK性能分析工具。针对移动平台,提供了实时监测和截帧分析功能,帮助您精准定位性能热点,提升应用的整体表现。 内存不足、内存泄漏和过度使用等问题,常常导致游戏出现卡顿、崩溃,甚至影响…...
OpenRestry(一个Nginx集成工具)的安装与使用
文章目录 一、OpenRestry介绍1、什么是Nginx呢?2、Nginx的反向代理3、Nginx的作用4、什么是OpenRestry? 二、OpenRestry的安装三、OpenRestry中nginx的使用1、Ngnix可以当做web服务器2、Nginx中可以编写Lua脚本 一、OpenRestry介绍 要想了解什么是OpenR…...
linux操作系统的基本命令
1.linux下的文件系统 在linux操作目录下没有像window操作系统下盘符的概念,只有一个根目录/,所有文件目录都在它的下面 linux的目录结构: 在Linux系统中: 文件都从跟目录开始的,用/表示文件名称区分大小写路径都是以/俩进行分隔(windown用\分隔)以.开头的文件为隐藏文件 Li…...
通过UV快速计算品牌独立站网络流量
背景: 品牌独立站项目交付过程中,我们需要为客户提供“云资源” 成本报价,其中“计算资源” 及CPU、内存、存储 参数相对固定,而互联网网络成本需要进行评估报价,以海外TOP云平台 AWS、AZURE、GCP 为例都是以“不限带…...
使用Kong开源API网关的保姆级教程
什么是Kong? Kong是一个开源的、云原生、高性能的API网关,可以轻松地为任何服务提供管理、保护和扩展。它提供了一个可扩展的插件生态系统,可以满足各种各样的需求,如身份验证、授权、限流、监控等。 安装Kong 1. 环境准备 操作系统: CentOS、Ubuntu等主流Linux发行版D…...
浅谈Spring Cloud:认识微服务
SpringCloud就是分布式微服务架构的一站式解决方案,是微服务架构落地的多种技术的集合。 目录 微服务远程调用 Eureka注册中心 搭建Eureka Server 注册组件 服务拉取 当各种各样的服务越来越多,拆分的也越来越细,此时就会出现一个服务集…...
mac命令行分卷压缩与合并
对当前目录内的文件压缩的同时分卷 //语法:zip -r -s 1m 压缩文件名.zip 当前路径 zip -r -s 1m split.zip . //解压 zip -s 0 split.zip --out unsplit.zip unzip unsplit.zip 将一个zip文件进行分卷 一个900k的压缩包名为hello.zip,将其分割为每500K一个zip zip - hello.…...
在 Linux (aarch64) 编译 OpenJDK 8
环境信息 操作系统:Rocky Linux 9.4 (aarch64)Open JDK:OpenJDK 8u422Boot JDK:jdk8u421-linux-aarch64 编译 OpenJDK 需要有一个 JDK。 解压后当前目录结构如下: /opt/ ├── jdk1.8.0_421 │ ├── COPYRIGHT │ ├──…...
如何有效检测住宅IP真伪?
在当今的互联网时代,住宅IP(即家庭用户通过宽带服务提供商获得的IP地址)在跨境电商、广告投放、网络安全等多个领域扮演着重要角色。然而,随着网络环境的复杂化和欺诈行为的增多,如何有效检测和辨别住宅IP的真伪成为了…...
springboot acuturator
SpringBoot使用Actuator - 基础使用步骤 Spring Boot 监控端点 Actuator 入门 - 系统学习 Spring Boot Admin入门 - 基础学习 Spring Boot 监控工具 Admin 入门 - 进阶学习 Spring Boot 监控平台 Prometheus Grafana 入门 Spring Boot 链路追踪 SkyWalking 入门...
什么是SaaS软件?有哪些常用的SaaS软件?
SaaS(Software as a Service,软件即服务)是一种通过互联网提供软件的模式,用户无需安装和维护任何复杂的基础设施,只需通过网络连接即可使用软件。SaaS 供应商负责软件的维护、升级和可用性,用户则通过订阅…...
QT Layout布局,隐藏其中的某些部件后,不影响原来的布局
最近在工作时,被要求,需要将布局中的某些部件隐藏后,但不能影响原来的布局。 现在记录解决方案! 一、水平布局(垂直布局一样) ui中的布局 效果: 按钮可以任意隐藏,都不影响其中布…...
WPF自定义Dialog模板,内容用不同的Page填充
因为审美的不同,就总有些奇奇怪怪的需求,使用框架自带的对话框已经无法满足了,这里记录一下我这边初步设计的对话框。别问为啥要用模板嵌套Page来做对话框,问就是不想写太多的窗体。。。。 模板窗体(XAML)…...
[数据集][目标检测]智慧养殖场肉鸡健康状态检测数据集VOC+YOLO格式4657张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):4657 标注数量(xml文件个数):4657 标注数量(txt文件个数):4657 标注…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践
在电商行业蓬勃发展的当下,多平台运营已成为众多商家的必然选择。然而,不同电商平台在商品数据接口方面存在差异,导致商家在跨平台运营时面临诸多挑战,如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...
