Skip to content

计蒜客 T1989 连续自然数和#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

对一个给定的自然数 ，求出所有的连续的自然数段（连续个数大于 1 ），这些连续的自然数段中的全部数之和为 。

例子：，所以从 到 的一个自然数段为 的一个解。

1.3. Input#

输入包含一个整数 。

1.4. Output#

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出的行按照第一个数从小到大排序，对于给定的输入数据，保证至少有一组解。

输出时每行末尾的多余空格，不影响答案正确性

1.5. Sample Input#

15

1.6. Sample Output#

1 5
4 6
7 8

1.7. Source#

计蒜客 T1989 连续自然数和

2. 解读#

STL基本使用。使用 STL中的队列 queue 来对元素进行入队出队操作。

若当前队内所有元素的和 ，则队首元素出队，直到。

若当前队内所有元素的和 ，则下一个元素入队。

在每次入队/出队完成以后，判断是否 ，若是，则输出。

3. 代码#

#include <iostream>
#include <queue>
using namespace std;

queue<int> qu;

int main()
{
    // test case
    int t;
    scanf("%d", &t);
    // 队首元素front, 队尾元素back
    int front, back;
    // 求和
    int sum = 0;
    // 输入
    for (int i = 1; i <= t; i++) {
        // 入队
        qu.push(i);
        // 累加
        sum += i;
        // 若求和大于要求
        while (sum > t) {
            sum -= qu.front();
            // 队首出队
            qu.pop();
        }
        // 获取队首元素
        front = qu.front();
        // 获取队尾元素
        back = qu.back();
        // 判断是否符合条件
        if (sum == t && front != back) {
            // 若符合要求，输出
            printf("%d %d\n", front, back);
        }
        // 若若求和小于要求，继续循环
    }
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top