题解 CF1409C 【Yet Another Array Restoration】
Suuon_Kanderu
2020-09-10 21:42:00
这题还是比较简单的，算是个模拟。
做这种题最重要的是思路清晰，现在真是颓废刷这种毫无思维含量的题还要 WA 一次。
思路：
1. 题目要求一个等差数列，我的思路是枚举公差。因为 $x,y \in {a_i}$ ，公差的取值范围是 $[1 , y - x]$ ， 超过 $y-x$ 肯定无法同时包含 $x$ 和 $y$。
2. 如果公差 $d$ 不是 $y-x$ 的因数，显然不满足条件。直接排除。然后我们假设现在的序列为 $ x ~,~ x + d ~,~ x + 2 \cdot d \cdots ~, ~y~$,此时序列长度 $len$ 为 $\frac{y-x} d + 1$。
3. 如果此时的 $len$ 已经超过了 $n$ 项，直接跳过。
3. 此时分情况讨论哪些满足条件，并记录答案：
1. 按照贪心，我们先向左边扩展一些,变成 $\cdots x - 2 \cdot d ~,~ x-d,~ x ~,~ x + d ~,~ x + 2 \cdot d \cdots ~, ~y~$。发现左边最多能够扩展 $\frac{x-1}{d}$ 个数。如果只要左边扩展或者不扩展就有 $\mathcal {n}$ 项，即 $len = \frac{y-x} d + 1 + \frac{x-1}{d} \ge n$。此时数列中的最大值为 $y$。
2. 如果还不够，我们只好向右扩展了。向右扩展 $n-len$项。此时数列中最大值为 $y + (n - cnt) \cdot d $ 。
代码就很简单了，理顺逻辑即可，细节较多。
```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
typedef long long ll;
const int N = 200000+100;
void work(int x , int y , int n) {
int ans = 0x7fffffff , d;
for(int i = 1; i <= y - x; i++) {
if(!((y - x) % i == 0))continue;
int cnt = 0;//即为 len
cnt += (y - x) / i + 1;
if(cnt > n)continue;
cnt += (x - 1) / i;
if( cnt >= n) {
if(y < ans)ans = y , d = i;
}else {
if(y + (n - cnt) * i < ans)
ans = y + (n - cnt) * i , d = i;
}
}
for(int i = 1; i <= n; i++)printf("%d " , ans) , ans -= d;
puts("");
}
int main() {
int t;scanf("%d" , &t);
while(t--) {
int x , y , n;
scanf("%d%d%d" , &n , &x , &y);
work(x , y , n);
}return 0;
}
```