cf 1512 E. Permutation by Sum

cf 1512 E. Permutation by Sum

題意：

我們定義排列的概念為：從1到n的整數組成的序列，每個數字隻出現一次

現在給你n,l,r,s,讓你構造一個長度為n的排列，使得其中的第l到第r項和為s

輸出任意答案

題解：

又是構造題，構造題考察經驗思維

我們想想區間[l,r]的和為s

區間長度為len = r - l+1

區間長度為len的能組成的最小和min就是1+…+len

最大和就是n+n-1…n-lenn+1

如果s不在這個範圍内，說明s無法構造，輸出-1

如果s可以構造說明最小和+？就是s

這個？怎麼求

ave = （s-min）/len：區間内每個數比最小值平均大Ave

那麼我們這個區間至少應該是i+ave（1<=i<=len）

這樣構造的區間一定小于等于s（我們去差為cha），且區間為從小到大順序排列

如果小于s（cha>0），我們就讓最後一位+1，cha–，如果cha還大于0，我們就讓倒數第二位+1，cha–，從後往前一次增加

為什麼這樣？

為什麼要+1呢？因為每位這個區間是最接近s的連續區間，是以從這個開始枚舉所需要的可能性最少

為什麼要倒着循環+1呢？因為這個循環肯定是不可能全部進行完的（因為我們已經求的原本的區間是最接近s的），是以在某個時刻cha會等于0，循環中斷，如果我們正着循環，在第i個數加完後中斷，第i個數就等于第i+1個數（因為原本序列是順序排列的，而i加了1，第i+1位沒變），會出現重複數，但是如果倒着循環就不會存在，因為後一位始終大于前一位

詳細看代碼

代碼：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define G 10.0
#define LNF 1e18
#define eps 1e-6
#define ll long long
#define INF 0x7FFFFFFF
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define SP system("pause")
#define mm(a, b) memset(a, b, sizeof(a))
#define fir(i, a, n) for (ll i = a; i <= n; i++)
#define rif(i, a, n) for (ll i = a; i >= n; i--)
#define each_cass(cass) for (cin >> cass; cass; cass--)
 
using namespace std;
void solve()
{
    ll n, l, r, s;
    cin >> n >> l >> r >> s;
    ll Min = (1 + r - l + 1) * (r - l + 1) / 2;
    ll Max = (n + n - r + l) * (r - l + 1) / 2;
    if (s > Max || s < Min)
    {
        cout << "-1" << endl;
        return;
    }
    int cha = s - Min;
    vector<int> zhong;
    vector<int> qian;
    vector<int> hou;
    int pingduo = cha / (r - l + 1);//代表[1~(r-l+r)]每個數至少要加的數
    int len = r - l + 1;
    for (int i = 1; i <= len; i++)
        zhong.push_back(i+pingduo),cha-=pingduo;
    if (cha)//如果cha不為0，就最大的幾個數+1直到cha=0
    {
        for (int i = zhong.size() - 1; cha && i >= 0; i--)
        {
            zhong[i]++;
            cha--;
        }
    }
    int vis[10000] = {0};//記錄，防止重複
    for (int i = 0; i < zhong.size(); i++)
        vis[zhong[i]] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (qian.size() == l - 1)//前面的數是(l-1)個
            break;
        if (!vis[i])
            qian.push_back(i), vis[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (hou.size() == n - r)//後面的數是(n-r)個
            break;
        if (!vis[i])
            hou.push_back(i), vis[i] = 1;
    }

    //輸出
    for (int i = 0; i < qian.size(); i++)
        cout << qian[i] << " ";
    for (int i = 0; i < zhong.size(); i++)
        cout << zhong[i] << " ";
    for (int i = 0; i < hou.size(); i++)
        cout << hou[i] << " ";
    cout << endl;
}
int main()
{
    int cass;
    each_cass(cass)
    {
        solve();
    }
    return 0;
}