做法:二分
思路
主要讲一下如何二分
分三种情况
1)一直下降
2)先上升再不变后下降,且不变的长度为1
3)先上升后下降
设第2、3种情况的最高峰为t
此时,从而求得注意会爆long long
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=100010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); __int128 n,h; inline __int128 read(){ __int128 x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } inline void write(__int128 x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); } bool check(__int128 x){ __int128 ans; if(x<=h){ ans=(1+x)*x/2; return ans-n<x; } __int128 t=h+x-1; if(t&1){ t/=2; ans=(h+t)*(t-h+1)/2+(1+t)*t/2+t; } else{ t/=2; ans=(h+t)*(t-h+1)/2+(1+t)*t/2; } return ans-n<t; } void solve(){ n=read();h=read(); __int128 l=1,r=n,ans; while(l<=r){ __int128 mid=(l+r)>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } write(ans); } int main(){ // ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }