本文主要是介绍【二分】【数学】有趣的水管,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
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);
}
这篇关于【二分】【数学】有趣的水管的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!