【二分】【数学】有趣的水管

2023-11-27 15:50
文章标签 二分 数学 有趣 水管

本文主要是介绍【二分】【数学】有趣的水管,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

P城想建立一条管道系统,城市中恰巧有n间房屋,市长想要每一间房屋都能通上自来水。

起初,市长只有一个可以供水的水管,和几个分离器。

分离器由一个输入口(输入口可以连接到水管或者上一个能流出水的输出管道)和x个输出口构成, 当分离器连接到水管时,水会从每个输出口流出。因为总水源只有一个,所以只有一根水管的入口可 以与水源连接。

在这里插入图片描述

市长有k - 1种分离器,每种分离器只有一个,k - 1种分离器的输出口分别为2,3,4 … k个。

现在需要有n户房屋通水,即恰好有n个输出口流出水来,市长至少需要多少个分离器呢?

输入格式

输入只有一行,包括两个用空格隔开的整数n和k(1 <= n <= 1e18,2 <= k <= 1e9)

输出格式

输出需要的最少分离器的数量,如果方案不存在则输出-1

输入输出样例
输入 #1
4 3
输出 #1
2
输入 #2
5 5
输出 #2
1
输入 #3
8 4
输出 #3
-1
说明/提示
数据范围

对于50%的数据,1 <= k <= 100
对于75%的数据,1 <= k <= 100000
对于100%的数据,1 <= k <= 1000000000

样例解释

样例一:
有4户人家以及输出口为2,3的分离器各一个,我们可以将3个输出口的分离器与水源连接,将2个输 出口的分离器连接到另一个分离器的一个输出口上,这样共有4个输出口可以流水。总共用到了2个分 离器,所以输出2。
样例二:
有5户人家以及输出口为2,3,4,5的分离器各一个,我们可以选择将输出口为5的分离器连接水 源。只用到了一个分离器,所以输出1。


解题思路

首先为了让分离器更少,所以肯定要优先选择更大的分离器
发挥一下草稿纸的作用,可以求出通式(?)
当选择x个分离器时,可以分离出 x * k - (x - 1) - (x - 1) * x / 2

二分选择mid个分离器


Code
#include <cstdio>
#include <iostream>using namespace std;unsigned long long n, m, l, r, mid, check, ans;int main(){scanf ("%lld%lld", &n, &m);l = 1, r = m - 1;ans = -1;while (l <= r){mid = (l + r) / 2;check = mid * m - (mid - 1) - (mid - 1) * mid / 2;//通式if (check >= n) r = mid - 1, ans = mid;else l = mid + 1;}printf ("%lld", ans);
}

这篇关于【二分】【数学】有趣的水管的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/427952

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta