[CF1305E] Kuroni and the Score Distribution

[CF1305E] Kuroni and the Score Distribution - 构造

Description

构造一个长度为 n 的，数字不超过 1e9 的，单调递增的，恰好有 m 个满足 (i<j<k) 且 (a_i +a_j=a_k) 的三元组 ((i,j,k)) 的序列。

Solution

要想让三元组个数最多，显然我们会按照 1,2,3,... 这样的方式构造。

注意在这个过程中，第 k 个元素（新加入）产生的贡献为 ((k-1)/2)。

如果我们想要添加的贡献不到 ((k-1)/2)，假设为 ((k-1)/2-x)，那么我们可以添加一个 (k+2x) 的元素。

按照以上的方法构造出的序列显然是最短的。

考虑如何补齐 n 个元素，我们可以从 1e9 向下抓若干个元素填在最后。

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    stringstream sout;
    int k = 0;
    while (m && n)
    {
        n--;
        ++k;
        int cur = min(m, (k - 1) / 2);
        if (cur < (k - 1) / 2)
            k += 2 * ((k - 1) / 2 - m);
        m -= cur;
        sout << k << " ";
    }
    while (n--)
    {
        sout << (int)(1e9 - n * k - n) << " ";
    }
    if (m)
    {
        cout << -1;
    }
    else
    {
        cout << sout.str();
    }
}