牛客练习赛51 E-数列

链接:https://ac.nowcoder.com/acm/contest/1083/E来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
Special Judge, 64bit IO Format: %lld

题目描述

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

输入描述:

第一行两个整数n,m。1<=n<=1e5,n<=m<=1e9。

输出描述:

一行n个整数,表示位置1…n填的数。

示例1

输入

复制

5 9

输出

复制

1 2 1 2 3

说明

小乔对数列的喜爱度为3,没有能使喜爱度大于3的方案了,此外1 2 3 1 2也是一个合法的方案

思路:

(抄取自官方题解)

对于一个数列,如果其一个子数列a[i],a[i+1]...a[j-1],a[j]满足a[k]=a[k-1]+1(i+1<=k<=j),同时,也满足i-1<1或者a[i]!=a[i-1]+1,j+1>n或者a[j+1]!=a[j]+1,则我们称这样的子数列为一段。我们可以发现,假如数列中有sum个这样的段,则小乔对数列的喜爱度为n-sum。因为数列是可以自由填数的,所以对与每一段我们使得a[i]=1是最优的,a[i],a[i+1]...a[j-1],a[j]显然。于是对于每一段,如果这段的长度为s,按最优的方法填数,则这一段的总和为s*(s+1)/2。
于是问题转换为:
把数列n分成sum个段,要求最小化sum,并且所有段的总和<=m。
设这sum段中长度最小的段长度为mn,长度最大的段长度为mx,可以发现如果我们已知了sum,那么要使这sum段的总和最小,就要使得mn和mx尽可能的接近,因为如果mx-mn>=2,那么段mx的最后一个元素的值为mx,段mn最后一个元素的值为mn,那么我们使段mx的长度-1,mn的长度加1。那么总和的变化就是总和=总和-mx+mn+1。因为mx-mn>=2,所以mx>mn+1。
因此如果得知sum,最优的策略就是均分所有段的长度。
均分的方法就是,首先使每一段的长度为n/sum,剩余n%sum个匀速均分配到n%sum个段上去。
于是有n%sum个段的长度为n/sum+1,n-n%sum个段的长度为n/sum。
对于sum,我们二分答案,因为答案具有单调性,分段越多,可以使总和越小。
通过二分答案求出sum再构造数列即可。时间复杂度O(logn+n)

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
ll m;
bool check(ll mid)
{
    // cout << mid << endl;
    ll s = n / mid;
    return s * (s + 1) / 2ll * (mid-n%mid) + (s + 1ll) * (s + 2ll) / 2ll * (n % mid) <= m;
}
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    gbtb;
    cin >> n >> m;
    ll l = 1ll;
    ll r = n;
    ll mid;
    ll ans;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        } else
        {
            l = mid + 1;
        }
    }
    for (int i = 1; i <= n % ans; ++i)
    {
        for (int j = 1; j <= n / ans + 1; ++j)
        {
            cout << j << " ";
        }
    }

    for (int i = 1; i <= ans - n % ans; ++i)
    {
        for (int j = 1; j <= n / ans; ++j)
        {
            cout << j << " ";
        }
    }
    cout << endl;


    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}