加载中...

分数问题善用移项：0902T2

发表于2023-09-03|OI（高中）2023-2024赛季

|总字数:141|阅读时长:1分钟|浏览量:

分数问题善用移项：0902T2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647332

其实就是分数规划，但不完全是。

对于求 $\Large\frac{\sum p_il_i}{\sum l_i}$ 在限定条件下的最大值，此类问题可以考虑 二分答案 并移项。

$\Large\frac{\sum p_il_i}{\sum l_i}\ge k$

$\Large\sum p_il_i\ge k\sum l_i$

$\Large\sum (p_i-k)l_i\ge 0$

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/66c6ab10

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

算法分数规划二分

相关推荐

【Loj #10012. 「一本通 1.2 例 2」Best Cow Fences】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669626.html 题目链接题目给定一个长度为 nnn 的非负整数序列 AAA ，求一个平均数最大的，长度不小于 LLL 的子段。思路先二分平均值。然后是判断。如何判断一段数中是否存在长度大于等于 LLL 且平均值大于某个数的子段呢？我们可以先让序列中的数都减去二分中的值，然后就转化为：序列中是否存在长度大于等于 LLL 的字段和为正。我们可以先构造一个前缀和。假设我们当前算到序列中的第 iii 项，我们只需要在前 i−...

【计蒜客T3668 Eye of the Storm】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16519140.html 题目链接题目思路方法一暴力循环 [l,r][l,r][l,r]，判断是否满足题意的数量，复杂度 O(n2q)O(n^2q)O(n2q) 方法二对于上面的方法，显然，其实我们可以只枚举有多少个满足 Sj=T2S_j=T_2Sj=T2，那么有多少个 iii 满足 Si=T1S_i=T_1Si=T1 是可以用前缀和预处理后 O(1)O(1)O(1) 算出来的。复杂度 O(nq)O(nq)O(nq) 方法三 ...

【SSOJ 4192 做题方案】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15795333.html 题目链接题目为了期末考取得好成绩，同学们都加倍努力进行复习。为了考得比其他同学好，小泽决定每一科都认真地多做1道题目，以提高对知识点的理解和熟悉程度！已知期末要考4门课，分别是《C++编程》、《算法入门》、《数据结构》、《搜索算法》，每一门课老师都准备了n道复习题，第一道题的耗时分别是a1、b1、c1、d1a_1、b_1、c_1、d_1a1、b1、c1、d1，第二道题的耗时分别是a2、b2、c2、d2a_...

【P1948 [USACO08JAN]Telephone Lines S】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16289494.html 题目链接题目 Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. The...

【P1661 扩散】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接题目一个点每过一个单位时间就会向四个方向扩散一个距离，如图。两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。思路二分答案+并查集。首先二分时间 ttt。如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...

【Loj #10011. 「一本通 1.2 例 1」愤怒的牛】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669383.html 题目链接题目农夫约翰建造了一座有间牛舍的小屋，牛舍排在一条直线上，第间牛舍在的位置，但是约翰的头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个...

数据加载中