『STA - R3』存在 题解

· · 题解

看到题面很容易想到形如 1,2,1,3,1,4,1,5,1,6\cdots 的序列。

很明显这个序列是不对的，因为如果选中类似 2,1,3 的子区间会发现不满足条件。

根据条件进行修改即可。

序列变为 1,2,1,1,3,1,1,4,1,1\cdots。

提交会发现有一个点不正确，因为这个方法不是最优的。

继续修改，把整个序列整体向前移一位。

序列变为 2,1,1,3,1,1,4,1,1,5\cdots。

这样便是最优的，因为省掉了开头不需要的 1，节省下来了一个位置。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a=2,b=0；
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        if(b==0){
            cout<<a<<" ";
            a++;
            b=2;
        }
        else{
            b--;
            cout<<1<<" ";
        }
    }
    return 0;
}

完结撒花。