转化限制+分析变量变化引起的答案变化:Gym - 104065D

https://vjudge.net/contest/587311#problem/H

先转化一波条件:

  • p i ≥ 1 X p_i\ge \frac 1 X piX1
  • p i ≤ 1 1 − Y p_i\le \frac 1 {1-Y} pi1Y1

所以我们按 p p p 排序, s u m x sum_x sumx 必然是后缀, s u m y sum_y sumy 必然是前缀。

同时发现在 X X X 变大, s u m x sum_x sumx 必然变大。 Y Y Y 同理。

观察式子:
在这里插入图片描述
假设 s u m y sum_y sumy 定,且 m a x y ∗ Y ≥ s u m x ∗ X max_y*Y\ge sum_x*X maxyYsumxX,则显然在满足条件下 X X X 越大越好。

然后就可以two-pointers了。

要去重,不然过不了 脑抽出题人卡精度

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 1000010
struct node {double p, c; 
}a[N];
int n, m, i, j, k, T;
double ans, S1[N], S2[N]; 
double x, y; 
int l, r; double calc_X(double p) {if(p==0) return -1; return 1.0/p; 
}double calc_Y(double p) {if(p==1) return -1; return 1.0/(1-p); 
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<=n; ++i) scanf("%lf%lf", &a[i].p, &a[i].c); sort(a+1, a+n+1, [] (node x, node y) { return x.p < y.p; }); a[n+1].p=1; for(i=1, j=0; i<=n+1; ++i) {if(a[i].p!=a[j].p) a[++j]=a[i]; else a[j].c+=a[i].c; } n=j; S1[0]=a[0].c; for(i=1; i<=n; ++i) S1[i]=S1[i-1]+a[i].c; for(i=n; i>=0; --i) S2[i]=S2[i+1]+a[i].c; 
//	for(i=0; i<=n; ++i) printf("%lf %lf\n", a[i].p, a[i].c); 
//	for(i=0; i<=n; ++i) printf("%lf ", S1[i]); printf("\n"); 
//	for(i=0; i<=n; ++i) printf("%lf ", S2[i]); printf("\n"); for(l=0, r=n; l<=n; ++l) {y=calc_Y(a[l].p); if(y<0) break; while(calc_X(a[r-1].p)>=0 && S2[r-1]*calc_X(a[r-1].p)<=S1[l]*y) --r; for(i=min(n, r+10); i>=max(1ll, r-10); --i) {x=calc_X(a[i].p); if(x<0) continue; if(i<=l) continue; 
//			printf("%lld %lld (%lf %lf)[%lf %lf] %lf\n", l, i, y, x, S1[l], S2[i], max(S1[l]*y, S2[i]*x)); ans=max(ans, S1[l]+S2[i]-max(S1[l]*y, S2[i]*x)); }}printf("%.11lf", ans); return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/159324.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

线性回归原理

1、 线性回归的原理 1.1 线性回归应用场景 房价预测 销售额度预测 金融:贷款额度预测、利用线性回归以及系数分析因子1.2 什么是线性回归 1.2.1定义与公式 线性回归(Linear regression)是利用回归方程(函数)对一个或多个自变量(特征值)和因变量(目标值)之间关系进行建模的…

VMware和Debian下载

文章目录 ⭐️写在前面的话⭐️一、VMware二、Debain三、建立虚拟机&#x1f680; 先看后赞&#xff0c;养成习惯&#xff01;&#x1f680;&#x1f680; 先看后赞&#xff0c;养成习惯&#xff01;&#x1f680; ⭐️写在前面的话⭐️ CSDN主页&#xff1a;程序员好冰 目前在…

模型UV纹理设置工具

1、什么是模型UV纹理&#xff1f; 模型的UV纹理是将二维纹理图映射到三维模型表面的过程。UV纹理可以为模型赋予颜色、纹理、细节和其他效果&#xff0c;使其看起来更加逼真。 2、UV纹理的原理 下面是模型UV纹理的详细原理介绍&#xff1a; UV坐标系统&#xff1a;UV坐标系统…

乐器经营商城小程序的作用是什么

乐器产品覆盖的人群非常广&#xff0c;小学生、老年人都有不小需求&#xff0c;也因此市场中的从业商家相对较多&#xff0c;产品丰富可供消费者选购&#xff0c;然而在实际经营中&#xff0c;线上线下面临痛点不少。 通过【雨科】平台搭建乐器小程序商城&#xff0c;将所有产品…

DarkGate恶意软件通过消息服务传播

导语 近日&#xff0c;一种名为DarkGate的恶意软件通过消息服务平台如Skype和Microsoft Teams进行传播。它冒充PDF文件&#xff0c;利用用户的好奇心诱使其打开&#xff0c;进而下载并执行恶意代码。这种攻击手段使用了Visual Basic for Applications&#xff08;VBA&#xff0…

JavaSE学习值之--认识异常

&#x1f495;"有效知识的前提是承认知识边界&#xff0c;承认我们对边界那边的一切无可奉告。"&#x1f495; 作者&#xff1a;Mylvzi 文章主要内容&#xff1a;JavaSE学习值之--认识异常 一.什么是异常&#xff1f; 异常就是程序在运行的时候产生的不正常的行为 …

多机器人三角形编队的实现

文章目录 前言一、机器人编队前的准备二、配置仿真环境2.编写机器人编队.cpp文件 三、三角形编队测试 前言 前阵子一直想要实现多机器人编队&#xff0c;找到了很多开源的编队代码&#xff0c;经过好几天的思索&#xff0c;终于实现了在gazebo环境中的TB3三角形机器人编队。 一…

SQL Server远程登录失败

SQL Server远程登录失败 检查SQL SERVER 是否允许远程访问. 具体步骤: 1)在远端SQL Server主机上,打开SSMS并连接数据库 2)在相应”数据库”上单击右键,选择”属性” 3)选择”连接”选项卡,检查”远程服务器连接”下,RPC服务是否选择. 设置SQL Server相关TCP连接 1.打开SQL Se…

Netty 入门 — 亘古不变的Hello World

这篇文章我们正式开始学习 Netty&#xff0c;在入门之前我们还是需要了解什么是 Netty。 什么是 Netty 为什么很多人都推崇 Java boy 去研究 Netty&#xff1f;Netty 这么高大上&#xff0c;它到底是何方神圣&#xff1f; 用官方的话说&#xff1a;Netty 是一款异步的、基于事…

KMP 算法 + 详细笔记

给两个字符串&#xff0c;T"AAAAAAAAB"&#xff0c;P"AAAAB"; 可以暴力匹配&#xff0c;但是太费时和效率不太好。于是KMP问世&#xff0c;我们一起来探究一下吧&#xff01;&#xff01;&#xff01; &#xff08;一&#xff09;最长公共前后缀 D[i] p[…

Java架构师缓存性能优化

目录 1 缓存的负载策略2 缓存的序列化问题3 缓存命中率低4 缓存对数据库高并发访问5 缓存数据刷新的策略5.1. 实时策略5.2. 异步策略5.3. 定时策略6 何时写缓存7 批量数据来更新缓存8 缓存数据过期的策略9 缓存数据如何恢复10 缓存数据如何迁移11 缓存冷启动和缓存预热想学习架…

解决react样式组合时css module动态样式失效的问题

现象&#xff1a; <button disabled{invalid} className{ "btn btn-primary btn-lg" invalid ? styles.btnDisabled : "" } > 注册 </button> 上面采用字符串拼接的方式&#xff0c;组合class&#xff0c;但是css module的动态样式style…

【Java零基础入门到就业】第一天:java简介和cmd窗口的一些常见命令

1、java简介 Java是一种基于类的、面向对象的编程语言&#xff0c;它被设计成具有尽可能少的实现依赖。它旨在让应用程序开发人员编写一次&#xff0c;并在任何地方运行(WORA)&#xff0c;这意味着编译后的Java代码可以在所有支持Java的平台上运行&#xff0c;而无需重新编译。…

【具身智能模型1】PaLM-E: An Embodied Multimodal Language Model

论文标题&#xff1a;PaLM-E: An Embodied Multimodal Language Model 论文作者&#xff1a;Danny Driess, Fei Xia, Mehdi S. M. Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, Wenlong Huang, Yevgen C…

Vue鼠标右键画矩形和Ctrl按键多选组件

效果图 说明 下面会贴出组件代码以及一个Demo&#xff0c;上面的效果图即为Demo的效果&#xff0c;建议直接将两份代码拷贝到自己的开发环境直接运行调试。 组件代码 <template><!-- 鼠标画矩形选择对象 --><div class"objects" ref"objectsR…

bash一行输入,多行回显demo脚本

效果图&#xff1a; 脚本&#xff1a; #!/bin/bash # 定义一个变量&#xff0c;用来存储输入的内容 input"" # 定义一个变量&#xff0c;用来存储输入的字符 char""# 为了让read能读到空格键 IFS_store$IFS IFS# 提示内容&#xff0c;在while循环中也有&a…

CSS 滚动驱动动画 animation-range

animation-range 语法 normallength-percentagetimeline-range-name 具名时间线范围 named timeline rangecovercontainentry 和 entry-crossingexit 和 exit-crossing 兼容性 animation-range 这个属性可同时对 scroll progress timeline 和 view progress timeline 这两种不…

数据结构与算法-(8)---队列(Queue)

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…

Python算法练习 10.15

leetcode 2130 链表的最大孪生和 在一个大小为 n 且 n 为 偶数 的链表中&#xff0c;对于 0 < i < (n / 2) - 1 的 i &#xff0c;第 i 个节点&#xff08;下标从 0 开始&#xff09;的孪生节点为第 (n-1-i) 个节点 。 比方说&#xff0c;n 4 那么节点 0 是节点 3 的孪…

LaunchView/启动页 的实现

1. 创建启动画板&#xff0c;LaunchScreen.storyboard 添加组件如图: 2. 项目中设置只支持竖屏&#xff0c;添加启动画板&#xff0c;如图: 3. 创建启动画面动画视图&#xff0c;LaunchView.swift import SwiftUI/// 启动视图 struct LaunchView: View {/// 字符串转换为字符串…