Codeforces Round #393 (Div. 2) - B
2024-10-07 12:50:38
题目链接: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();
}
}
最新文章
- [Linux] - Docker 常用命令
- Foundation和UIKit框架组织图
- EF实体框架之CodeFirst六
- 10分钟API Hook MessageBox
- C#SortedList排序列表怎么样逆序输出
- jq each 用法以及js与json互转
- Python3 配置文件 解析
- df 和 du 命令详解
- 每个QWidget都有contentsMargins函数,善用QMargins
- JAXB - Calling marshal
- 转:Xshell显示找不到匹配的outgoing encryption算法怎么办
- jQuery ZeroClipboard中Flash定位不准确的解决方案
- 【MongoDB】学习MongoDB推荐三本书
- Linux之父:除了写内核代码 别的真不会(转)
- 写一个Redis封装类
- Java学习笔记--异常描述
- springboot使用i18n时properties文件中文乱码
- 死磕 java集合之ConcurrentHashMap源码分析(二)——扩容
- 四则运算4(Android版)
- idea创建项目报错(Maven execution terminated abnormally (exit code 1) )解决方案
热门文章
- 【leetcode】447. Number of Boomerangs
- javaSE之运行时异常和编译时异常
- IBatis.Net 下使用SqlBulkCopy 大批量导入数据 问题解决
- MongoDB性能分析
- Mysql 链接数据库时区错误
- 怎样用idhttpserver代替IIS让用户浏览html或下载文件 http://bbs.csdn.net/topics/360248674
- mysql一主多从配置详情
- 腾讯两大开源项目Tars、TSeer
- PHP点滴记录
- JavaScript.convertArray