牛客练习赛51 E-数列

E-数列

题目链接：https://ac.nowcoder.com/acm/contest/1083/E

题目描述：
小乔有一个长度为n的整数数列，最开始里面所有的值都为0，小乔需要将在1…n的每一个位置填入一个大于0的正整数，得到一个新的数列，并且这个数列所有数的和不超过m，小乔对这个数列会有一个喜爱度，小乔对这个数列的喜爱度为满足2<=i<=n并且a[i]=a[i-1]+1的i的个数。现在给出n,m，请你制定一种填数方案，最大化小乔对数列的喜爱度。方案可能有多种，你只需要输出任意一种即可。

题解：

我们先定义一个如果对于一段数列a[i],a[i+1]...a[j-1],a[j] 如果a[k]=a[k-1]+1(i+1<=k<=j)同时也满足a[i]!=a[i-1]+1||a[j+1]!=a[j]+1,我们称这样一段数列为段，假设数列中有sum段这样的数列，最大

喜爱度为n-sum,因为我们可以自由填数，对于任意一段可以填为（1，2，3...S)则其和为s*（s+1）/ 2；

所以我们要使sum尽可能地小，并且所有段的总和要小于m；

因此我们可以二分查找sum并且均分n，这样我们就能的到n/sum个段，其他的n%sum平分到n/sum段上，所以最后得到n%sum个长度为n/sum+1的段和sum-n%sum段长度为n/sum段

最后输出就行了

官方题解：https://m.nowcoder.com/discuss/248083?&headNav=acm

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
bool judge(ll mid)
{
    return (n/mid+1)*(n/mid+2)/2*(n%mid)+(n/mid)*(n/mid+1)/2*(mid-n%mid)<=m;
}
void solve(ll ans)
{
    ll cnt=1;
    for(int i=1;i<=n%ans;i++)
    {
        for(int j=1;j<=n/ans+1;j++)
        {
            cout<<j<<(cnt++==n?'
':' ');
        }
    }
    for(int i=1;i<=ans-n%ans;i++)
    {
        for(int j=1;j<=n/ans;j++)
        {
            cout<<j<<(cnt++==n?'
':' ');
        }
    }
}
int main()
{
    cin>>n>>m;
    ll l=1,r=n;
    ll ans=n;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(judge(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    solve(ans);
    return 0;
 }