\(数学题，式子并不难推，但边界是真的烦\)
\(\color{Red}{Ⅰ.其实可以发现,当m>=n时,每次都可以粮食补到n,所以一定是在第n天消耗完毕}\)
\(\color{Purple}{Ⅱ.当n>m时,前m天每次粮食都补到n}\)
\(设从m+1天开始,需要mid天消耗完毕\)
\(因为每天都可以加m粮食,所以mid天可以加X_{补充}=(mid-1)*m粮食(因为第m+1天是补满前一天的，所以是mid-1)\)
\(然后麻雀带走的粮食用等差数列计算m+1,m+2,...,m+mid\)
\[也就是X_{消耗}=mid*(m+1)+(mid-1)*mid/2
\]
\]
然后因为消耗的粮食要大于补充的粮食
\[得到X_{消耗}>=n+X_{补充}
\]
\]
\[化简得到m+mid*(mid+1)/2>=n可行
\]
\]
\(根据这个二分即可。\)
\(但是r的边界多少呢?我因为这个wa了无数次,边界应该是r=2e9\)
\(这样二分的时候刚好不会超过long long\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,ans;
int main()
{
cin>>n>>m;
if(n<=m)
{
cout<<n;
return 0;
}
ans=m;//有m天补不全
ll l=0,r=2e9,mid;
while(r>l)
{
mid=(l+r)/2;
if(m+mid*(mid+1)/2>=n) r=mid;
else l=mid+1;
}
cout<<ans+r;
}
原文链接: https://www.cnblogs.com/iss-ue/p/12837354.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/346665
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
