解题思路
设数组为 a1,a2,…,an，满足
- ai≥0
- ∑i=1nai=m
- 相邻不同的位置数不超过 d
并定义
P4681.第2题-不稳定or相似
题目内容
给定两个整数n,m，你需要构造一个长度为 n的非负整数数组a={a1,a2,…,an}，使其元素总和满足：
∑i=1nai=m
定义相邻差和：
F(a)=∑i=1n−1∣ai−ai+1∣
本题有 q 次独立询问。第j次询问给出一对整数 (d,y)，你最多只能让数组中 “相邻数值不同” 的边（我们将i(1≤i≤n−1)视为第i 条边，连接相邻元素 ai 与 ai+1）的数量不超过 d，即：
#{i∈[1,n−1]∣ai=ai+1}≤d
并问在该限制下，是否存在某个数组 a 使F(a)≥y。若存在，输出 YES；否则输出 NO。
注意：不同询问彼此独立，均基于同一对 (n,m)重新构造数组。
输入描述
每个测试文件均包含多组测试数据：
-
第一行输入一个整数t(1≤t≤104)，表示测试用例数量。
-
对于每个测试用例：
- 第一行输入三个整数 n,m,q(1≤n≤109;0≤m≤109;1≤q≤2×105)；
- 此后 q行，每行输入两个整数d,y(0≤d≤n−1;0≤y≤1018)。
-
除此之外，保证全部测试用例的 q之和不超过 2×105。
输出描述
对于每个询问，输出一行 YES或 NO，表示是否存在满足限制的数组 a 使F(a)≥y。
样例1
输入
2
5 7 5
0 0
1 7
1 8
2 14
2 15
1 3 2
0 0
0 1
输出
NO
YES
NO
YES
NO
YES
NO
说明
对测试用例一，n=5,m=7：
- 若 d=0,y=0：数组必须为常数列，但m mod n=0无法构造，输出 NO；
- 若d=1,y=7：取[7,0,0,0,0]，边数为 1，F=7≥7，输出 YES；
