cf 1512 E. Permutation by Sum

題意：

我們定義排列的概念為：從1到n的整數(shù)組成的序列，每個數(shù)字只出現(xiàn)一次
現(xiàn)在給你n,l,r,s,讓你構(gòu)造一個長度為n的排列，使得其中的第l到第r項和為s
輸出任意答案

題解：

又是構(gòu)造題，構(gòu)造題考察經(jīng)驗思維
我們想想?yún)^(qū)間[l,r]的和為s
區(qū)間長度為len = r - l+1
區(qū)間長度為len的能組成的最小和min就是1+…+len
最大和就是n+n-1…n-lenn+1
如果s不在這個范圍內(nèi)，說明s無法構(gòu)造，輸出-1
如果s可以構(gòu)造說明最小和+？就是s
這個？怎么求
ave = （s-min）/len：區(qū)間內(nèi)每個數(shù)比最小值平均大Ave
那么我們這個區(qū)間至少應(yīng)該是i+ave（1<=i<=len）
這樣構(gòu)造的區(qū)間一定小于等于s（我們?nèi)ゲ顬閏ha），且區(qū)間為從小到大順序排列
如果小于s（cha>0），我們就讓最后一位+1，cha–，如果cha還大于0，我們就讓倒數(shù)第二位+1，cha–，從后往前一次增加
為什么這樣？
為什么要+1呢？因為每位這個區(qū)間是最接近s的連續(xù)區(qū)間，所以從這個開始枚舉所需要的可能性最少
為什么要倒著循環(huán)+1呢？因為這個循環(huán)肯定是不可能全部進行完的（因為我們已經(jīng)求的原本的區(qū)間是最接近s的），所以在某個時刻cha會等于0，循環(huán)中斷，如果我們正著循環(huán)，在第i個數(shù)加完后中斷，第i個數(shù)就等于第i+1個數(shù)（因為原本序列是順序排列的，而i加了1，第i+1位沒變），會出現(xiàn)重復(fù)數(shù)，但是如果倒著循環(huán)就不會存在，因為后一位始終大于前一位
詳細看代碼

代碼：

#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)]每個數(shù)至少要加的數(shù)int len = r - l + 1;for (int i = 1; i <= len; i++)zhong.push_back(i+pingduo),cha-=pingduo;if (cha)//如果cha不為0，就最大的幾個數(shù)+1直到cha=0{for (int i = zhong.size() - 1; cha && i >= 0; i--){zhong[i]++;cha--;}}int vis[10000] = {0};//記錄，防止重復(fù)for (int i = 0; i < zhong.size(); i++)vis[zhong[i]] = 1;for (int i = 1; i <= n; i++){if (qian.size() == l - 1)//前面的數(shù)是(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)//后面的數(shù)是(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; }

總結(jié)

以上是生活随笔為你收集整理的cf 1512 E. Permutation by Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。