本文主要是介绍Codeforces 785C Anton and Fairy Tale (规律+二分查找),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门
找规律, 容易发现 当第m 天后 粮仓容量开始减少, 每天递增的数目是 以公差为1的等差数列, 前n项和为 n*(n+1)/2 所以
通俗的讲就是 二分查找 Sn>= n-m 即为结果;
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <vector>
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e18+2;
const int MOD=1e9+7;
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){ return b/gcd(a,b)*a;}
ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x)%MOD;x=(x*x)%MOD;}return res;}int main()
{ ll n,m;while(~scanf("%I64d %I64d",&n,&m)){ll ans;ll mid;ll le=0,ri=maxn;if(n<=m){ans=n;printf("%I64d\n",ans);continue; } while(le<ri){mid=(le+ri)/2;if(mid*(mid+1)/2>=n-m){ri=mid;}else le=mid+1;}printf("%I64d\n",le+m);}
}
//570441179141911871 511467058318039545
这篇关于Codeforces 785C Anton and Fairy Tale (规律+二分查找)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!