首页 > 其他分享 >题解- 恢复数组

题解- 恢复数组

时间:2025-01-07 19:04:02浏览次数:16  
标签:10 20 int 题解 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,表示有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;
}

标签:10,20,int,题解,50,数组,恢复,等差数列
From: https://blog.csdn.net/qq_73162098/article/details/144847678

相关文章