山东大学考研机试--AcWing 3717. 整数序列

题目描述

很多整数可以由一连串的整数序列（至少两个数）相加而成，比如 25=3+4+5+6+7=12+13。输入一个整数 N，输出 N
的全部整数序列，如果没有则输出 NONE。

输入格式

一个整数 N。

输出格式

每行输出一个满足条件的整数序列。

序列内部元素从小到大排序。

优先输出首项更小的序列。

数据范围

2⩽N⩽1e7

输入样例

25

输出样例

3 4 5 6 7
12 13

题意分析

首先看到是将一个数拆为连续的一段序列，实际上就是求在整数的序列中求是否有一段的连续的和，此时我们就应该警觉，因为其包含使用二分法的两个关键要素：

• 一段有序的序列（整数序列）
• 一个查找条件（序列内各数的和为n）
  因此我们就要考虑使用二分法
  y总的二分法模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

所以对于这道题只需要根据从a到b的连续的大小为（a+b)/2*(b-a+1)

CODE

#include<iostream>
using namespace std;
#define int long long
const int N=1e7+10;
int n;
bool st;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n/2;i++)
    {
        int l=i+1,r=n/2+1;
        while(l<r)
        {
            int mid=l+r>>1;
            int x=(i+mid)*(mid-i+1)/2;//二分的条件 标准的二分模板
            if(x>=n)r=mid;
            else l=mid+1;
        }
        if((i+r)*(r-i+1)/2==n)
        {
            for(int j=i;j<=r;j++)cout<<j<<' ';
            cout<<endl;
            st=1;
        }
    }
    if(!st)puts("NONE");
    
    return 0;
}