Codeforces Round #713 (Div. 3) E（思维）

E. Permutation by Sum

题目链接

题意：

给你一个排列（1到n每个数字都出现且只出现一次），要求你用排列中的数字构造一个新数组，使得下标为l到r的数字之和等于s。

分析：

题目可以理解为，让你在1-n中挑k（r-l+1）个数字和为s。首先可以知道可以组成的数的理论最大值为 \displaystyle \sum_{i = n-k}^n i，理论最小值为\displaystyle \sum_{i = 1}^k i，并且处于这个范围之内的数都可以被正确的表示出来。故，只要s处于最小值和最大值之间就有解。

剩下就是如何找这k个数，定义两个函数：low(k)表示\displaystyle \sum_{i = 1}^k i,high(k,n) 表示\displaystyle \sum_{i = n-k}^n i，即分别表示从1-n中取k个的最小值和最大值。我们令i = n，如果high(k, i) >= s && low(k - 1) <= s - i则表示i这个数字可以选取。其中式子的前半段表示，从1-i这些数中取k个数可以表达出s，后半段表示，如果选取i，那么在剩下的数中取k-1个数也可以表示出s-i，那么i这个数可以选用。

代码