文章目录

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

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

例子： 1998 + 1999 + 2000 + 2001 + 2002 = 10000 1998+1999+2000+2001+2002=10000 1998+1999+2000+2001+2002=10000，所以从 1998 1998 1998 到 2002 2002 2002 的一个自然数段为 M = 10000 M=10000 M=10000 的一个解。

1.3. Input

输入包含一个整数 M ( 10 ≤ M ≤ 2 , 000 , 000 ) M(10 \le M \le 2,000,000) M(10≤M≤2,000,000)。

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 来对元素进行入队出队操作。

若当前队内所有元素的和 s u m > M sum > M sum>M，则队首元素出队，直到 s u m ≤ M sum \le M sum≤M。

若当前队内所有元素的和 s u m ≤ M sum \le M sum≤M，则下一个元素入队。

在每次入队/出队完成以后，判断是否 s u m = M sum = M sum=M，若是，则输出。

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，有问题欢迎通过邮箱交流。