cf176B. Pipeline

前端之家收集整理的这篇文章主要介绍了cf176B. Pipeline前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
  1. //题目连接:<a target=_blank href="http://codeforces.com/contest/287/problem/B">点击打开链接</a>
  1.  
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. inline long long sum(long long a,long long k){
  5. return k*(k+1)/2-(k-a)*(k-a+1)/2-a+1;
  6. }
  7. int f(long long n,long long k){
  8. long long i,tot=1+(k-1)*k/2;
  9. if(n>tot) return -1;
  10. int toright=0;
  11. long long l=0,r=k,mid=(l+r)/2;//the numbers,have to take into account that l+1=r;uncontinue
  12. while(l<=r){
  13. long long tmp=sum(mid,k);
  14. if(tmp==n)break;
  15. else if(tmp<n){
  16. if(sum(mid+1,k)>=n){//对于mid个排水口,有2,3,...,mid+1的min,也有k,k-1,k-2,k-mid+1的max,而我的sum表示的是max,//sum(mid)和sum(mid+1)之间不是连续的,所以加上if判断,修正
  17. toright=1;
  18. break;
  19. }
  20. l=mid+1;
  21. mid=(l+r)/2;
  22. }
  23. else{
  24. if(sum(mid-1,k)<n) break;
  25. r=mid-1;
  26. mid=(l+r)/2;
  27. }
  28. }
  29. return mid+toright;
  30. }
  31.  
  32. int main(){
  33. long long n,k;
  34. scanf("%I64d%I64d",&n,&k);
  35. cout<<f(n,k)<<endl;
  36. return 0;
  37. }

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