题意
要求我们还原原数组arr
,给定了原数组的几种特性:
1、包含n
个正整数
2、包含两个已知的正整数x
,y
,且 (x<y)
3、原数组中的每两个相邻正整数之间的差值相同,即:(a_2−a_1=a_3−a_2=…=a_n−a_{n−1})
最后要求输出原数组,答案可能不唯一,要求使原数组中最大的一个数的值尽可能地小,即:尽可能让 (max(a_1,a_2,…,a_n)) 最小
解题思路
1、我们尝试让 x 到 y 中尽可能地填满剩下的(n-2)个值,尽管可能填不下,则尽可能地添加更多,剩下的优先添到 x 的左侧,当左侧添不了,则在添到 y 的右侧,直到输出了 n 个数为止。
2、计算 x 到 y 需要加多少个 k。可以用暴力枚举来计算: (m=(x-y))枚举 n 到 1 直到(k%m=0),此时,x 到 y 需要加 (k÷m) 个 k。
3、输出以上枚举的数,接下来还需要输出 (n-(k+1)) 个数,方法在第 1 条。
代码实现
#include <iostream>
using namespace std;
void solve ( void )
{
int n, l, r;
cin >> n >> l >> r;
int x = r - l, k = n - 1, t = l;
while ( x % k != 0 ) k--;
x /= k;
cout << l << ' ';
for ( int i = 0; i < k; i++ )
{
t += x;
cout << t << ' ';
}
n -= ( k + 1);
while ( n )
{
l -= x;
if ( l > 0 )
{
cout << l << ' ';
n--;
} else {
break;
}
}
while ( n )
{
t += x;
cout << t << ' ';
n--;
}
cout << endl;
}
int main ( void )
{
int T;
cin >> T;
while ( T-- ) solve();
return 0;
}