当前位置: 代码迷 >> 综合 >> 牛客-序列和(等差数列)
  详细解决方案

牛客-序列和(等差数列)

热度:103   发布时间:2023-10-11 08:24:47.0

题目描述
给出一个正整数N和长度L,找出一段长度大于等于L的连续非负整数,他们的和恰好为N。答案可能有多个,我我们需要找出长度最小的那个。
例如 N = 18 L = 2:
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的,但是我们输出更短的 5 6 7
输入描述:
输入数据包括一行: 两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)
输出描述:
从小到大输出这段连续非负整数,以空格分隔,行末无空格。如果没有这样的序列或者找出的序列长度大于100,则输出No

示例1
输入
18 2
输出
5 6 7

分析:

求的是长度最小的序列和能组成目标值N,连续之和容易想到等差数列求和公式为Sn=n*a1+n(n-1)d/2,在这里d为1,通过观察输出可以想到Sn就是本题中的N(已知),只要知道第一项a1以及项数n(对应题目中的L,n的范围为[L,100])。进而可以改写公式得到 a1 = (2 * Sn - n * (n - 1))/ (2 * n) ,随后用项数作为循环的条件,计算第一次(n最少)能得到首项为整数时即为所求子序列。
ps :
(1) 转换公式的时候尽可能减少除法的次数,要考虑除法后保留小数
(2)注意N输入的值很大,要用long定义类型,对应的cout结果时也要用long
(3)强制类型转换的用法 (double),(long)等

#include <iostream>
using namespace std;
void findNums(long N, int L){
    double a = 0;for(int i = L; i <= 100; i++){
    a = (double)(2 * N - i * (i - 1)) / (2 * i);// 说明a是个整数if(a - long(a) == 0){
    for(int j = 0; j < i; j++){
    if(j < i - 1) cout << (long)(a + j) << " ";else cout << (long)(a + j);                }break; // 第一次遇到的整数解a,就是最小的了,因为遍历的i是元素个数}if(i == 100) cout << "No" ;}
}
int main(){
    long N, L;while(cin >> N >> L);findNums(N, L);return 0;
}