本篇题解为此题较简单做法,请放心阅读。
题目简述
一共有 \(n\) 个格子,给定两个整数 \(A,B\) 分别位于第 \(1\) 和第 \(n\) 格,中间有 \(n−2\) 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 \([C,D]\) 之间。
依次输入 \(n,a,b,c,d\)。
若能,输出 YES
;反之输出 NO
。
思路
遇事不决先看数据范围,发现数据范围 \(3 \le N \le 5 \times 10^5\),那么时间复杂度在 \(O(N)\) 以内就可以接受,本篇题解就详细解释一下 \(O(N)\) 的算法。
首先可以想到 \(O(N)\) 的复杂度就是遍历 \(N\),可以想到枚举在 \(A,B\) 之间填了 \(i\) 个数,从 \(0 \sim N-2\) 遍历即可,遍历时进行判断,如果满足要求可直接输出 YES
,否则遍历完后输出 NO
。
接着可以先把区间 \([C,D]\) 转化为区间 \([0,D-C]\),那么判断条件就需要判断 \(C\) 的合法性及可行性:
\[B - (2 \times (i + 1) - N) \times C \]接着可写出判断条件的边界条件,首先是最大值即右区间,通过右区间 \(D-C\) 很容易得出:
\[A + i \times (D - C) + D \]以及左区间:
\[A + (N - 2 - i) \times (C - D) + C \]如果合法的 \(C\) 在此区间内则输出 YES
,否则在遍历后输出 NO
。
注意:因为均为闭区间,所以需是 \(\le\) 而不是 \(<\)。
经过以上分析及转化,很容易即可得出代码了。
\[\text{The End!} \] 标签:输出,agc017,题解,times,le,遍历,区间 From: https://www.cnblogs.com/So-noSlack/p/17582280.html