AOJ 1309.lls和神话故事
265
题目
lls上体育课遇到一个朋友,这个人很会说故事,而且都是神话故事。
这一天lls想听故事了,于是找到了这个朋友,朋友说了一个故事:
很久很久以前…有一个皇帝,他很富有,有很多很多稻米,并且让许多建筑家一起建筑了一个粮仓,专门用来盛放稻谷,容量是n粒稻米,已经装满了。让建筑家没想到的是,稻米是好东西,鸟儿也喜欢吃。为了让皇帝满意,每天早上会有人固定向里面加m粒稻谷(但不能超过容量)。而每天晚上会有鸟儿来偷吃稻米,并且每天会增加一只鸟儿(第一天1只,第二天2只……),每只鸟儿一次吃一粒稻米。如果晚上剩下的稻米不够鸟儿吃了,那没吃到的鸟儿只能回去睡觉了。
朋友故事还没说完,lls脑海中瞬间想到稻米终将会吃完,并一会儿就指出了粮仓第一次为空的那天。现在你要完成同样的事。
第一行为两个整数n(1≤n,m≤10^18),分别表示粮仓的容量和每天早上加入的稻米数。
从第一天早上开始计天数(即第一天晚上会有鸟儿来吃)
输出粮仓第一次为空的那天
样例一:
5 2
样例二:
8 1
样例一:
4
样例二:
5
题解
手算一下,可以发现前m天,鸟吃的都刚好能被补上
而m天后,前m只鸟消耗每天的补给,剩下的鸟消耗仓库的存粮
因此计算
(1+t)*t/2 >= n
即可解出最小的符合要求的
t
然后加上 m
就是答案由于数据非常大,可以使用
unsigned long long
解方程部分使用二分查找
n最大为
1e18
,解集取为1e10
确保覆盖所有解如果n<m,那么直接输出n
代码
#include <cstdio> #include <iostream> #include <cmath> using namespace std; typedef unsigned long long LL; LL n,m; // (1+t)*t/2 >= m min(t)+m int main(){ cin.sync_with_stdio(false); cin.tie(0); cin >> n >> m; LL l=0,r=1e10; LL t=0; while(l<r){ t = (l+r)/2; if(t*(t+1) >= (n-m)*2) r = t; else l = t + 1; // cout << l <<" " << r << endl; } cout << l + m << endl; return 0; }