传送门：送你去985D；
题意：
你有n袋沙包，在第一个沙包高度不超过H的条件下，满足相邻两个沙包高度差小于等于1的条件下（注意最小一定可以为0），求最少的沙包堆数；
思路：
画成图来说，有两种可能，一种是y=h-x一次函数和常函数y=x组合，还有一种是先上升后下降的函数，注意斜率绝对值都是1；
二分答案，具体来说，我是二分了最大高度，主要是check（）比较要思考，（昨天晚上没有细心写check，错过了很多AC：）；
这个check中；如果最大高度 mid 比m小，说明不会有折线，直接考虑三角形加矩形的情况。
如果最大高度mid 比m大，考虑三角形，和最大高度左边的情况，利用贪心，左边区域的最低一定是m。
上面的情况中，如果区域的容量比较宽裕（比n大）就放大答案，否则缩小；
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <list> #include <iterator> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define Pll pair<ll,ll> #define Pii pair<int,int> #define fi first #define se second #define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) typedef long long ll; typedef unsigned long long ull; /*-----------------show time----------------*/ ll n,m,ans = 2e18+9; ll cal(ll x) { return 1ll*x*(x+1)/2; } bool check(ll x) { ll st = cal(x); ll tmp = x; //计算完整三角形区域; if(x<=m) { if(st<=n) { tmp = tmp+ 1ll*((n-st)/x); if((n-st)%x)tmp++; ans = min(tmp,ans); return true; } else { return false; } } else { if(st<=n) { ll y = n - st; //n中剩下的 ll q = x - m -1; //区域左边 ll c = cal(q) + 1ll* m *(x-m);// if(c > y)return false; tmp += x-m; //因为第一个也算，所以不减1; y -= c; tmp = tmp + y/x; if(y%x!=0)tmp++; //显然，如果还有多余，一定比x（最大值）小，找个适当位子插入就ok ans = min(ans,tmp); return true; } else return false; } } int main(){ OKC; cin>>n>>m; ll le = 1, ri = 1ll*2e10; //我是二分整个区域的最大值。 while(le <= ri) { ll mid = (le + ri)>>1; // cout<<mid<<endl; if(check(mid)) { le = mid + 1; } else ri = mid - 1; } cout<<ans<<endl; return 0; }