东坑网站建设公司,网站商场模板,如何查看网站流量,电脑制作app的软件cf 1512 E. Permutation by Sum
题意#xff1a;
我们定义排列的概念为#xff1a;从1到n的整数组成的序列#xff0c;每个数字只出现一次 现在给你n,l,r,s,让你构造一个长度为n的排列#xff0c;使得其中的第l到第r项和为s 输出任意答案
题解#xff1a;
又是构造题
我们定义排列的概念为从1到n的整数组成的序列每个数字只出现一次 现在给你n,l,r,s,让你构造一个长度为n的排列使得其中的第l到第r项和为s 输出任意答案
题解
又是构造题构造题考察经验思维 我们想想区间[l,r]的和为s 区间长度为len r - l1 区间长度为len的能组成的最小和min就是1…len 最大和就是nn-1…n-lenn1 如果s不在这个范围内说明s无法构造输出-1 如果s可以构造说明最小和就是s 这个怎么求 ave s-min/len区间内每个数比最小值平均大Ave 那么我们这个区间至少应该是iave1ilen 这样构造的区间一定小于等于s我们去差为cha且区间为从小到大顺序排列 如果小于scha0我们就让最后一位1cha–如果cha还大于0我们就让倒数第二位1cha–从后往前一次增加 为什么这样 为什么要1呢因为每位这个区间是最接近s的连续区间所以从这个开始枚举所需要的可能性最少 为什么要倒着循环1呢因为这个循环肯定是不可能全部进行完的因为我们已经求的原本的区间是最接近s的所以在某个时刻cha会等于0循环中断如果我们正着循环在第i个数加完后中断第i个数就等于第i1个数因为原本序列是顺序排列的而i加了1第i1位没变会出现重复数但是如果倒着循环就不会存在因为后一位始终大于前一位 详细看代码
代码
#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;vectorint zhong;vectorint qian;vectorint hou;int pingduo cha / (r - l 1);//代表[1~(r-lr)]每个数至少要加的数int len r - l 1;for (int i 1; i len; i)zhong.push_back(ipingduo),cha-pingduo;if (cha)//如果cha不为0就最大的几个数1直到cha0{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;
}
