题解- 恢复数组

题目描述

有一个数组a[1…n]，但是这个数组的内容丢失了，你要尝试恢复它。已知以下的三个事实：
1、对于1<=i<=n，都有a[i]>0，且所有的a[i]互不相同。即a数组保存的全部都是正整数，且互不相同。
2、x和y一定是属于数组a，且x<y。
3、a数组是递增的数组，且相邻两项的差是相等的。即数组a是等差数列。
容易发现，同时满足上面三个条件的a数组不一定是唯一的。你要输出使得a[n]的值最小的那个a数组。

输入
多组测试数据。
第一行，一个整数T，表示有T组测试数据。
接下来有T行，每行3个整数：n,x,y。

输出
共T行，每行n个整数。
样例输入 Copy
5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22
样例输出 Copy
1 49
10 20 30 40 50
20 26 32 38 44 50
3 8 13 18 23
1 4 7 10 13 16 19 22 25
提示
对于100%的数据满足：1≤T≤100,2≤n≤50，1≤x,y≤50。

题意

有一个数组a[1…n]，但是这个数组的内容丢失了，你要尝试恢复它。已知以下的三个事实：

1、对于1<=i<=n，都有a[i]>0，且所有的a[i]互不相同。即a数组保存的全部都是正整数，且互不相同。

2、x和y一定是属于数组a，且x<y。

3、a数组是递增的数组，且相邻两项的差是相等的。即数组a是等差数列。

容易发现，同时满足上面三个条件的a数组不一定是唯一的。你要输出使得a[n]的值最小的那个a数组。

输入T组数据，每组数据包含n,x,y三个数。

（给定条件补全数组的题目）

分析

1.数组中的每个数都大于0，且互不相同。

2 .y和x存在于数组中。

3 .数组是递增的等差数列。

我们可以求出x和y的差p，那么等差数列的差一定就是p的因数

又因为要求a[n]最小的，所以公差一定是p的最小因数

除此之外，x和y之间的数（包括x，y）的个数一定小于等于n

把握这三点就能求出答案

代码

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int maxx = 1e9;
        int ans;
        int n, x, y;
        cin >> n >> x >> y;
        int p = y - x;
        for (int i = 1; i <=p;i++)
        {
            if(p%i==0)
            {
                if(p/i<n)
                {
                    int u = n - p / i;
                    x = x - (u) * i;
                    int count = 0;
                    int j = 1;
                    while(1)
                    {
                        j++;
                        if(x + (j - 1) * i<=0)//只输出大于0的数
                        {
                            continue;
                        }
                        cout << x + (j - 1) * i << " ";
                        count++;
                        if(count==n)//输出n个停止即可
                        {
                            break;
                        }
                    }
                    break;
                }
            }
            continue;
        }
        cout << endl;
    }
    return 0;
}