CF1772C 题解

# Different Differences ## 题面翻译 共 $t$ 组询问，定义一个数组的特征数为 **相邻两数差的不同值的个数**。例如数组 $[1,3,4,7,8]$ 的相邻数差为 $[2,1,3,1]$，共有 $ 个不同的值，即原数组的特征数为 $。构造一个长度为 $k$ 且数组中每个数都不超过 $n$ 的一个 **严格递增数组**，使其的特征数尽可能大。输出这个数组。 \le t\le 819,1\le k\le n\le 40$。 ## 题目描述 An array $ a $ consisting of $ k $ integers is strictly increasing if $ a_1 < a_2 < \dots < a_k $ . For example, the arrays $ [1, 3, 5] $ , $ [1, 2, 3, 4] $ , $ [3, 5, 6] $ are strictly increasing; the arrays $ [2, 2] $ , $ [3, 7, 5] $ , $ [7, 4, 3] $ , $ [1, 2, 2, 3] $ are not. For a strictly increasing array $ a $ of $ k $ elements, let's denote the characteristic as the number of different elements in the array $ [a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}] $ . For example, the characteristic of the array $ [1, 3, 4, 7, 8] $ is $ 3 $ since the array $ [2, 1, 3, 1] $ contains $ 3 $ different elements: $ 2 $ , $ 1 $ and $ 3 $ . You are given two integers $ k $ and $ n $ ( $ k \le n $ ). Construct an increasing array of $ k $ integers from $ 1 $ to $ n $ with maximum possible characteristic. ## 输入格式 The first line contains one integer $ t $ ( $ 1 \le t \le 819 $ ) — the number of test cases. Each test case consists of one line containing two integers $ k $ and $ n $ ( $ 2 \le k \le n \le 40 $ ). ## 输出格式 For each test case, print $ k $ integers — the elements of the strictly increasing array $ a $ with the maximum possible characteristic. If there are multiple answers, print any of them. ## 样例 #1 ### 样例输入 #1 ``` 7 5 9 4 12 3 3 3 4 4 4 4 6 8 11 ``` ### 样例输出 #1 ``` 1 3 4 7 8 2 4 7 12 1 2 3 1 3 4 1 2 3 4 2 4 5 6 1 2 3 5 6 7 8 11 ``` --- --- --- 看完题目，我们可以发现两个要点： 1. 特征数为相邻两数差的不同值的个数。 2. 特征数尽可能大。 3. 输出的是严格递增数列。 提示：此题输出不唯一，样例只需理解，程序输出不应该全等于样例。 --- 我们以样例第一组输入数据为例讲解。 ``` 5 9 ``` 首先我们容易想到造一个差为 $[1,2,3,4\ldots]$ 的数列，我们定义为数列 $A$，我们直接输出看看。 ```cpp for(int i = 1; i <= k; i++) cout << 1 + i * (i - 1) / 2 << " "; ``` ``` 1 2 4 7 11 ``` 但是题目要求每个数都不超过 $n$，也就是说，到这个数列中的其中一个数时，我们已经使特征数尽可能大了，后面的差为多少都无所谓了，只要数值不超过 $n$。 所以我们应该构建另一个长度为 $k$ 数列 $B$，存的是 $[n-k+1,n]$。 ```cpp for(int i = 1; i <= k; i++) cout << n - k + i << " "; ``` ``` 5 6 7 8 9 ``` 我们可以发现，当 $B_i$ 刚刚好大于 $A_i$ 时，我们已经尽可能让特征数大了，所以说，第 $i$ 个数为 $\min(a_i,b_i)$。 --- 代码： ```cpp #include <iostream> #define min(a,b) (a<b?a:b) using namespace std; int t,k,n; //处理 handle inline void handle(){ for(int i = 1; i <= k; i++){ int ha = 1+i*(i-1)/2;//A_i int hb = n-k+i;//B_i int mi = min(ha,hb); printf("%d ",mi); } } int main(){ scanf("%d",&t); while(t--){ scanf("%d %d",&k,&n); handle(); printf("\n"); } return 0; } ```