QwQ和刷墙

发表于 更新于 分类于 本文字数： 970 阅读时长 ≈ 4 分钟

Description

QwQ非常喜欢玩部落冲突，但他从来不升级城墙，所以他的城墙开始时全都是1级的。

一天QwQ心血来潮，他先把他的个城墙排成一排，然后在脑中构思好每个城墙要被升到几级。

然而QwQ发现给每个城墙升到他想要的等级，不多升也不少升并不是一件容易的事，因为部落冲突只支持每次将一段城墙升高一级。

形式化地说，你的每次操作只能选择一对满足，然后将第到第块城墙各升高一级。

由于QwQ比较懒，他需要最小化操作的次数，把墙刷到他想要的等级。（具体输出方式见输出格式）

与真实游戏不同的是，你不能调换城墙的顺序。

Input

第一行包括一个整数表示QwQ的城墙个数。

第二行包括个整数。表示第块城墙QwQ想要刷到的级别。

Output

第一行输出一个整数，表示你的操作次数，如果有多种操作次数最小的操作方式，你可以输出任何一个。（保证操作次数的最小值在以内）

接下来行，每行2个整数表示你给第到第个城墙每块升了一级。

原来的城墙等级为

差分就变成了

于是对进行差分并将第一项减一，接下来要操作的就是对数列各项归零。

显然总操作数就等于数列所有正项之和。

为了优化过程，所以尝试构建两个差分数列分别代表中的正项和负项并舍弃0项。（为了操作便利，对数列取绝对值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
    int left[100086], right[100086], leftc[100086], rightc[100086],res=0,cntl=2,cntr=1,last,now,x,fz=1;
    /*leftc和rightc分别代表L和R数列，right和left数组分别记录leftc和rightc各项指向的墙块序号/
    scan(last);/*last记录上一输入值*/
    left[1] = 1;
    leftc[1] = last - 1;
    res += last - 1;
    f(i, 2, x)
    {
        scan(now);
        if (now > last)
        {
            res += now - last;
            left[cntl] = i;
            leftc[cntl++] = now - last;
        }
        if(now<last){
            right[cntr] = i;
            rightc[cntr++] = last - now;
        }
        last = now;
    }

这样的话，就可以在输入后直接开始输出了

先输出一个左界，然后输出右界，如果右界在数组没有，就输出边界值

而上面差分出来的和就代表指向的墙块序号要输出的次数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define pn(x) printf("%d", x)
    pn(res);
    f(i,1,cntl-1){
        while(leftc[i]--)
            {
                printf("\n%d ", left[i]);
                if(rightc[fz]>0){
                    printf("%d", right[fz]-1);
                    rightc[fz] -= 1;
                    if(rightc[fz]==0)
                        fz += 1;
                }
                else
                    printf("%d", x);
            }
    }

于是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>

#define max(x, y) x < y ? y : x
#define min(x, y) x < y ? x : y
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define sqr(x) (x) * (x)
#define f(i, a, b) for (int i = a; i <= b; i++)
#define pn(x) printf("%d", x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))
int left[100086], right[100086], leftc[100086], rightc[100086],res=0,cntl=2,cntr=1,last,now,x,fz=1;

int main()
{
    //IN;
    //OUT;
    scan(x);
    scan(last);
    left[1] = 1;
    leftc[1] = last - 1;
    res += last - 1;
    f(i, 2, x)
    {
        scan(now);
        if (now > last)
        {
            res += now - last;
            left[cntl] = i;
            leftc[cntl++] = now - last;
        }
        if(now<last){
            right[cntr] = i;
            rightc[cntr++] = last - now;
        }
        last = now;
    }
    pn(res);
    f(i,1,cntl-1){
        while(leftc[i]--)
            {
                printf("\n%d ", left[i]);
                if(rightc[fz]>0){
                    printf("%d", right[fz]-1);
                    rightc[fz] -= 1;
                    if(rightc[fz]==0)
                        fz += 1;
                }
                else
                    printf("%d", x);
            }
    }
    return 0;
}