CF1862B Sequence Game 题解

分析#

很简单的一道构造题。

因为第一个数是必取的，所以只需要从第二个数开始判断，即如果 $b_{i-1}\le b_i$ ，就不需要在这两个数之间添加别的数。

反之，如果不满足，我们就需要在这两个数之间添加一个 $b_i$ ，这样就可以保证它满足 $b_{i-1}\le b_i$ 的条件。

所以我们只需要先跑一次循环计算出 $m$ 的值，将 $m$ 和 $a_1$ 提前输出，然后循环输出剩下的数即可。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define int ll
5
const int MaxN = 1e6 + 100;
6
const int INF = 1e9;
7
int T=1, N, M;
8
template<class T>
9
inline void qread(T &sum)
10
{
11
    sum=0;int boo=1;
12
    char x=getchar();
13
    while(x<'0'||x>'9'){if(x=='-')boo=-1;x=getchar();}
14
    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
15
    sum*=boo;
16
}
17
template<class T>
18
void qput(T x)
19
{
20
    if(x<0){
21
        x=-x;
22
        putchar('-');}
23
    if(x>9)
24
        qput(x/10);
25
   putchar(x%10+48);
26
}
27
inline void Solve()
28
{
29
    int n;
30
    cin>>n;
31
    int a[2000010];
32
    for(int i=1;i<=n;i++){
33
        cin>>a[i];
34
    }
35
    int m=1;
36
    //cout<<a[1]<<" ";
37
    for(int i=2;i<=n;i++){
38
        m++;
39
        if(a[i]>=a[i-1]){//如果不满足条件长度就需要加一
40
            //m++;
41
            continue;
42
        }
43
        m++;
44
    }
45
    cout<<m<<endl<<a[1]<<" ";//a1直接输出即可，循环从2开始
46
    for(int i=2;i<=n;i++){
47
        if(a[i]>=a[i-1]){
48
            cout<<a[i]<<" ";
49
        }
50
        else{
51
            cout<<a[i]<<" "<<a[i]<<" ";
52
        }
53
    }
54
    cout<<endl;
55
}
56
signed main()
57
{
58
    //freopen(".in", "r", stdin);
59
    //freopen(".out", "w", stdout);
60
    ios::sync_with_stdio(0);
61
    //cin.tie(0);
62
    cin >> T;
63
    while (T--)
64
       Solve();
65
    //fclose(stdin);
66
    //fclose(stdout);
67
    return 0;
68
}