题目链接: Game With Array
给定n和s, 表示你需要构造出一个仅由正整数组成, 且长度为n序列, 使得序列中元素总和为s.
问: 你能否找到这样的一个序列, 并且选定出一个k(k∈[0,s]k∈[0,s]k∈[0,s]), 使得从序列中任选若干个元素, 总和不等于k, 也不等于s-k. 若能, 则输出一种合法的序列和k.
解题思路
构造 我看这个题的博客题解很多人都乱写呀, 估计自己都不太明白吧 (我其实也不明白).
首先我们考虑如果我们按照1, 2, 4, 8, … 这样去构造序列, 那我们一定可以满足任意的k. 因为我们这样构造出来的序列, 彼此都是不可替代的, 因此覆盖k的区间是最广的.
那么对于本题而言, 我们在构造序列时, 实际上希望覆盖尽可能少的k, 这样我们才能满足题意.
那么结合上面的思路来看, 我们应当希望构造出的序列尽可能的彼此可以替代.
那这相当于我们希望序列中重复的元素尽可能多. 因为一个元素自身是自身的完全替代.
现在我们希望用n个正整数凑出s, 最好的方式是什么? n-1个1和1个s-(n-1).
那这样我们能表示的k的区间为: [0,n−1]∪[s−n&＃43;1,s][0, n-1] \cup [s-n&＃43;1, s][0,n−1]∪[s−n&＃43;1,s].
如果我们希望能找到一个合法的k∈(n−1,s−n&＃43;1)<&＃61;&＃61;>k∈[n,s−n]k∈(n - 1, s - n &＃43; 1) <&＃61;&＃61;> k∈[n, s - n]k∈(n−1,s−n&＃43;1)<&＃61;&＃61;>k∈[n,s−n], 那么应满足 n≤s−nn ≤ s - nn≤s−n &＃61;&＃61;> 2∗n≤s2 * n ≤ s2∗n≤s.
因此, 当满足2∗n≤s2 * n ≤ s2∗n≤s时, 我们一定可以构造出一个合法序列, 并取k &＃61; n满足题意.
当2∗n>s2 * n > s2∗n>s时, 我们一定无法构造出合法序列. (可以自行推导选多个2, 多个3的情况, 并不会取得更优策略.)
AC代码
#include
#define rep(i, n) for (int i &＃61; 1; i <&＃61; (n); &＃43;&＃43;i)
using namespace std;
typedef long long ll;
int main()
{int n, s; cin >> n >> s;if (n * 2 > s) puts("NO");else {puts("YES");rep(i, n - 1) printf("%d ", 1);printf("%d\n", s - (n - 1));printf("%d\n", n);}return 0;
}
END
京公网安备 11010802041100号