Pipeline（codeforces）

设计模式 前端之家
前端之家收集整理的这篇文章主要介绍了Pipeline（codeforces），前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
B. Pipeline
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
@H_301_29@

Vova,the Ultimate Thule new shaman,wants to build a pipeline. As there are exactlynhouses in Ultimate Thule,Vova wants the city to have exactlynpipes,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) andxoutput 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.

The figure shows a4-output splitter

Vova has one splitter of each kind: with2,3,sans-serif">4,...,sans-serif">koutputs. 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 exactlynpipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.

@H_301_29@
Input

The first line contains two space-separated integersnandk(1 ≤ n ≤ 1018,sans-serif">2 ≤ k ≤ 109).

Please,do not use the%lldspecifier to read or write 64-bit integers in С++. It is preferred to use thecin,coutstreams or the%I64dspecifier.

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.

Sample test(s)
@H_301_29@
input 

4 3
output 

2
5 5
1
8 4
-1



数据量很大，二分查找是个不错的选择。

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <map>

@H_301_206@ using namespace std;

typedef long long ll;


int main(){

ll n,k;

while (cin>>n>>k) {

//int flag = 1;

ll low=0,high=k,mid;

while(low<=high)

{

mid=(low+high)>>1;

ll s = mid*k-(mid-1)*(mid+2)>>1;

if(n>s)

low=mid+1;

else

high=mid-1;

}

if(low > k)

cout<<"-1"<<endl;

else

cout<<low<<endl;

}

return 0;

}

原文链接：https://www.f2er.com/javaschema/285745.html

猜你在找的设计模式相关文章

适配器模式-让不兼容的接口得以适配
适配器模式将一个类的接口转换成客户期望的另一个接口，使得原本接口不兼容的类可以相互合...
策略模式-定义一个算法族
策略模式定义了一系列算法族，并封装在类中，它们之间可以互相替换，此模式让算法的变化独...
设计模式之高质量代码
设计模式讲的是如何编写可扩展、可维护、可读的高质量代码，它是针对软件开发中经常遇到的...
模板方法模式-封装一套算法流程
模板方法模式在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中，使得子类可以在...
迭代器模式-统一集合的遍历方式
迭代器模式提供了一种方法，用于遍历集合对象中的元素，而又不暴露其内部的细节。
单例模式的五种实现方式及优缺点
单例模式（Singleton Design Pattern）保证一个类只能有一个实例，并提供一个全局访问点。
组合模式-统一的处理个别对象与组合对象
组合模式可以将对象组合成树形结构来表示“整体-部分”的层次结构，使得客户可以用一致的方...
装饰者模式-动态的包装原有对象的行为
装饰者模式能够更灵活的，动态的给对象添加其它功能，而不需要修改任何现有的底层代码。
观察者模式-将消息通知给观察者
观察者模式（Observer Design Pattern）定义了对象之间的一对多依赖，当对象状态改变的时候...
代理模式-访问对象的代理而非其本身
代理模式为对象提供一个代理，来控制对该对象的访问。代理模式在不改变原始类代码的情况下...
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript