CF contest 985 D贪心、二分

时间:2022-12-30 00:17:30

Problem

http://codeforces.com/contest/985/problem/D

题目大意:

给你一个n和h

把n分解为一些数的和,要求第一个数 <= h ,最后一个数为1,且相邻数之间的差值的绝对值不大于1

问分解的数的数量最少是多少?

思路

首先,若没有数h的限制,那最优的分法是**从后往前**1,2,3,…,x 使得sum=n 。 若不等,则再加上那个差值即可(放到相同的数那里) 比如 n = 18 h = 10 则分法为 5,4,3,3,2,1 即18-15=3 所以有两个3

然后,考虑h的限制,那我第一个数一定取h,后面的数,满足“山峰”形状,如下图

CF contest 985 D贪心、二分

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;
}