题目链接:http://codeforces.com/contest/760/problem/B

题意:给定n张床,m个枕头,然后给定某个特定的人(n个人中的其中一个)他睡第k张床,问这个人最多可以拿多少个枕头。保证n个人每个人至少
有一个枕头并且相邻两个人的枕头数目之差不能大于等于2.

思路:二分这个人的枕头数,然后就是总枕头数目最小=睡他左边的人的枕头数目都比右边少一个+睡他右边的人的枕头数目都比左边少一个+他的枕头数。
假设当前二分的的枕头数为val,那么左右两边的最小数目为以val为首项,-1位公差的等差数列。 还要注意不能出现负数,所以当某一人的数目为1时其他都
为1.

import java.io.PrintWriter;
import java.util.*; public class Main {
static long cal(long a1,long d,long n){
a1=Math.max(a1, 1); //至少有一个。
long k=Math.min(n,a1); //k个构成等差序列
return k*a1+k*(k-1)/2*d+(n-k); //等差序列求和+剩余都为1
}
static long check(long val,long k,long n){
return cal(val-1,-1,k-1)+cal(val-1,-1,n-k)+val; //左边+右边+自己
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
long n=cin.nextLong(),m=cin.nextLong(),k=cin.nextLong();
long L=1,R=(m-(n-1)),mid;
while(R>=L){ //二分。
mid=(L+R)/2;
if(check(mid,k,n)>m){
R=mid-1;
}else{
L=mid+1;
}
}
out.println(R);
cin.close();
out.flush();
}
}

最新文章

  1. [Linux] - Docker 常用命令
  2. Foundation和UIKit框架组织图
  3. EF实体框架之CodeFirst六
  4. 10分钟API Hook MessageBox
  5. C#SortedList排序列表怎么样逆序输出
  6. jq each 用法以及js与json互转
  7. Python3 配置文件 解析
  8. df 和 du 命令详解
  9. 每个QWidget都有contentsMargins函数,善用QMargins
  10. JAXB - Calling marshal
  11. 转:Xshell显示找不到匹配的outgoing encryption算法怎么办
  12. jQuery ZeroClipboard中Flash定位不准确的解决方案
  13. 【MongoDB】学习MongoDB推荐三本书
  14. Linux之父:除了写内核代码 别的真不会(转)
  15. 写一个Redis封装类
  16. Java学习笔记--异常描述
  17. springboot使用i18n时properties文件中文乱码
  18. 死磕 java集合之ConcurrentHashMap源码分析(二)——扩容
  19. 四则运算4(Android版)
  20. idea创建项目报错(Maven execution terminated abnormally (exit code 1) )解决方案

热门文章

  1. 【leetcode】447. Number of Boomerangs
  2. javaSE之运行时异常和编译时异常
  3. IBatis.Net 下使用SqlBulkCopy 大批量导入数据 问题解决
  4. MongoDB性能分析
  5. Mysql 链接数据库时区错误
  6. 怎样用idhttpserver代替IIS让用户浏览html或下载文件 http://bbs.csdn.net/topics/360248674
  7. mysql一主多从配置详情
  8. 腾讯两大开源项目Tars、TSeer
  9. PHP点滴记录
  10. JavaScript.convertArray