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

P4653 [CEOI 2017] Sure Bet

题目描述

现在有 n 个A类灯泡和 n 个B类灯泡,每个灯泡都有各自的权值。

我们将这些灯泡分为 n 组,每组包含一个来自A类的灯泡和一个来自B类的灯泡。

你可以从中选取任意个灯泡,每选取一个灯泡需要花费 1 的代价。

在你选取完之后,系统会随机在A类和B类中选择一个类型,并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。

现在请你合理选取灯泡,以最大化可能的最小收益。你只需要求出来这个收益即可。

输入格式

第一行一个正整数 n ,表示灯泡的组数。

接下来 n 行每行两个空格隔开的实数 Ai​,Bi​​​。分别表示属于这组的A灯泡和B灯泡的权值。输入的实数不会超过四位小数。

输出格式

输出最大化的最小可能收益,请输出到小数点后恰好四位。

输入输出样例 #1

输入 #1

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

输出 #1

0.5000

说明/提示

样例解释

最优策略是选择第一组的B灯泡和第三组的A灯泡和第四组的A灯泡:

  • 如果B类灯泡被点亮,收益是 3.7−3=0.7。
  • 如果A类灯泡被点亮,收益是 1.6+1.9−3=0.5。

最小可能收益是 0.5。

数据范围

对于所有测试点,有 1.0≤Ai​,Bi​≤1000.0,0≤n≤105。

代码参考

#include<bits/stdc++.h>
using namespace std;int n;
double ans;
double A[100001], B[100001];
bool t[100001][2]; bool cmp(double a, double b) 
{return a > b;
}int main() 
{scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%lf %lf", &A[i], &B[i]);sort(A + 1, A + n + 1, cmp);sort(B + 1, B + n + 1, cmp);double a = 0.0, b = 0.0;for(double i = 1, j = 1; i <= n && j <= n;) {int x = i, y = j; a += A[x] * double(!t[x][0]);b += B[y] * double(!t[y][1]);t[x][0] = t[y][1] = 1;  // 标记已遍历的数据 ans = max(ans, min(a - i - j, b - i - j));  // 计算价值 if(a >= b) j++;if(a <= b) i++;}printf("%.4lf\n", ans);  // 输出保留4位小数return 0;
}
http://www.hskmm.com/?act=detail&tid=31154

相关文章:

  • 20251014
  • PHP虚拟主机测试页面
  • 歌词本。 - Slayer
  • 10月14日
  • 使用 Docker 快速搭建 MinIO 文件存储服务
  • 2025.10.14 正睿二十连测
  • singleton_pattern
  • ai出题
  • Python的Numpy、Pandas和Matplotlib(随笔)
  • 财务怎样做到业财融合 - 智慧园区
  • CF2146E
  • Spring Boot项目中集成Spring Security OAuth2和Apache Shiro
  • 【博客导航】
  • 部署向量数据库milvus
  • 从 0 到 1 实现高性能日志库 MiniSpdlog — 这可能是最适合新手的日志系统实战项目 !
  • 思想惰性:警惕时代中的精神惯性
  • journalctl 查看服务日志
  • 对ssh修改源码过程
  • 低代码时代,企业机遇在哪里
  • 2025 年浙江专升本培训学校推荐榜:浙江/台州/萧山/温州专升本机构,聚焦学历提升需求,杭州泓涵培训学校为学子护航
  • 25noip20d2t2 马戏表演 - Slayer
  • 从后端转行为AI工程师,转行AI大模型开发,附全套学习资源!收藏这份指南! - 实践
  • 实验一:现代C++初体验
  • 2025秋_11
  • 软件工程学习日志2025.10.14
  • CF1784E
  • nSwitch 存档自动备份系统模块 - autoSAVE
  • java基础7-字符串
  • 乐云具身活动体验
  • 【技术解决方案】联邦学习中遇到的Non-IID问题——隐语SecretFlow