CodeForces - 287B-Pipeline（二分）
Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes, each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there's water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters.
A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there's water flowing out from it. At most one splitter can be connected to any water pipe.
Vova has one splitter of each kind: with 2, 3, 4, ..., k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it's impossible.
Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.
Input
The first line contains two space-separated integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 109).
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Output
Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.
Examples
Input
4 3
Output
2
Input
5 5
Output
1
Input
8 4
Output
-1代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,k;
bool f(long long mid) {
long long s;
s=(k+1)*k/2-mid*(mid-1)/2-(k-mid);
if(mid==k) s=mid;
if(s>=n) return true;
else return false;
}
int main() {
scanf("%lld%lld",&n,&k);
long long sum=0;
sum=k*(k+1)/2-k+1;
long long ans=k-1;
long long l=2,r=k+1;
long long mid=(l+r)/2;
if(sum<n) {
printf("-1\n");
} else if(n==1) {
printf("0");
} else {
while(mid-l>0) {
//mid=(l+r)/2;
if(f(mid)) {
l=mid;
mid=l+(r-l)/2;
} else {
mid=l+(mid-l)/2;
}
}
long long ans=0;
ans=k+1-mid;
printf("%lld\n",ans);
}
return 0;
}
最新文章
- Yii2的深入学习--事件Event
- Mac通过终端显示和隐藏 隐藏文件
- 推荐相关学习 & 典型算法、典型特征、典型推荐系统框架
- 转 浅谈算法和数据结构: 十 平衡查找树之B树
- cmake gcc等安装备案
- 在Linux下给mysql创建用户并分配权限及问题解决方案
- python函数的参数
- windows关机命令
- 160923、项目管理模式:如何去除SVN标记
- SQL将金额转换为汉子
- Cocos2dx 多线程
- 利用__index和__newindex实现默认值表、监控表、只读表（转）
- 第八周 ip通信基础回顾
- LeetCode174-Dungeon Game-数组，动态规划
- 站在DevOps肩膀上的TestOps（一）
- 算法竞赛入门经典训练指南——UVA 11300 preading the Wealth
- 我们的团队-IT梦想队
- Docker 容器入门
- oracle 替换字符串中指定位置内容
- Spring boot 集成 mybaits plus（代码生成器）