Problem
http://codeforces.com/contest/985/problem/D
题目大意:
给你一个n和h
把n分解为一些数的和,要求第一个数 ,最后一个数为1,且相邻数之间的差值的绝对值不大于1
问分解的数的数量最少是多少?
思路
首先,若没有数h的限制,那最优的分法是**从后往前**1,2,3,…,x 使得sum=n 。 若不等,则再加上那个差值即可(放到相同的数那里) 比如 则分法为 5,4,3,3,2,1 即18-15=3 所以有两个3
然后,考虑h的限制,那我第一个数一定取h,后面的数,满足“山峰”形状,如下图
H是固定的
所以,我这里的做法是,枚举最高峰的“高度”(可以算出这些点的和),显然若高度越大,则这些数的和越大,点也越多。
那我可以二分,求出满足要求n的最低峰,则当前的点数即为最小。
要注意的是,一个最高峰对应两种方案 ,即最大点值是一个还是两个,都要计算。
代码示例
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,h;
bool check(ll m)
{
ll t=m*(m+1)/2;
if(t>=n) return true;
return false;
}
bool check1(ll m)
{
ll ans1=0;
ans1+=(h+m)*(m-h+1)/2;
ans1+=(m-1)*m/2;
if(ans1>=n) return true;
ll ans2=ans1;
ans2+=m;
if(ans2>=n) return true;
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
ios::sync_with_stdio(false);
while(cin>>n>>h){
ll l=-1,r=2e9;
while(r-l>1)
{
ll mid=(r+l)/2;
if(check(mid)) r=mid;
else l=mid;
}
if(r*(r+1)/2!=n) r--;
//cout<<"***"<<r<<endl;
if(h>=r){
if(r*(r+1)/2<n) cout<<r+1<<endl;
else cout<<r<<endl;
}
else{
l=h-1,r=2e9;
while(r-l>1)//二分最高的值是多少
{
ll mid=(r+l)/2;
if(check1(mid)) r=mid;
else l=mid;
}
//cout<<"r: "<<r<<endl;
ll ans1=0;
ans1+=(h+r)*(r-h+1)/2;
ans1+=(r-1)*r/2;
if(ans1>=n) cout<<r-h+r<<endl;
else{
cout<<r-h+r+1<<endl;
}
}
}
return 0;
}