「常见优化技巧」和例题分析

这篇文章，将要分析luogu题单「【算法2-2】常见优化技巧」中的所有题目。

在讲解的过程中，会了解到许多常见的优化技巧。

看完此文，你就会解决上述题单里的所有题目，及一下题目：

P1102 A-B 数对
P1638 逛画展
P1115 最大子段和
P7072 [CSP-J2020] 直播获奖
P2671 [NOIP2015 普及组] 求和
P4147 玉蟾宫
P2866 [USACO06NOV] Bad Hair Day S
P1950 长方形
P2032 扫描
P2216 [HAOI2007] 理想的正方形
UVA11572 唯一的雪花 Unique Snowflakes
P4653 [CEOI2017] Sure Bet
P3143 [USACO16OPEN] Diamond Collector S
P7910 [CSP-J 2021] 插入排序
P1578 奶牛浴场
P3467 [POI2008] PLA-Postering
P1886 滑动窗口 /【模板】单调队列
P2880 [USACO07JAN] Balanced Lineup G
P1714 切蛋糕
P1725 琪露诺

P1102 A-B 数对

这个题目的大致意思就是在一组数中找到一对 $A,B$ ，使得他们满足 $A-B=C$

这题首先也是最容易想到的思路就是双重循环枚举法，不用说，这种方法必定超时，这里不做过多的介绍。

如本文标题所言，我们要学习「常见优化技巧」，这里就介绍一个方法——转换法。

我们可以把原有的条件、等式等进行转化，变成另一种更易计算的形式。

如这题的式子就可以转换为 $A-C=B$ 。

也就是说，我们只要判断是否有一个数比 $A$ 小 $C$ ，如果有，那么就加上其个数。

这让人很容易想起来「桶」算法。但是，这一题的数据范围比较大，所以我们就要用到 c++ 自带的 STL ， map 。

其实并不是什么高级的东西，只不过是一个可以开的非常大的数组，调用方法等和普通数组没有区别。

确定下来了思路，我们就可以开始写了。不过这里有一个比较坑的地方，就是题目输入的数组是没有排序的，所以需要手动排序。这样，时间复杂度就是 $O(nlogn)$

cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll, ll> t;
ll a[200000 + 10];
int main() {
    ll n, c;
    cin >> n >> c;
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        t[a[i]]++;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        cnt += t[a[i] - c];
    }
    cout << cnt;
    return 0;
}

当然，我们还可以进行优化，我们把中间的sort(a + 1, a + 1 + n);也就是排序去掉也可以。

因为即使这个时候没有排序了，但是我们已经把 cnt += t[a[i] - c]; 单独放在了一个 for 里面，所以这种情况下不会有少算比它小的数的情况，因为所有的数都录入完了，而 cnt 加的顺序其实是无所谓的。

所以，以下是最终优化的程序

cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll, ll> t;
ll a[200000 + 10];
int main() {
    ll n, c;
    cin >> n >> c;
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        t[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cnt += t[a[i] - c];
    }
    cout << cnt;
    return 0;
}

P1638 逛画展

这个题目的主要意思非常的明显。首先，我们定义一个区间内的数如果囊括了 $M$ 位画家，我们就称其为「满足条件的区间」，则问这个区间的长度的最小值。

这个题目要用到一个非常常见的优化技巧 ——「滑动窗口」（当然，这个算法还有很多的名字，重点只算法的本质）

我们维护一个窗口——或者说区间。左端点是 l，右端点是r。

我们要保证这个区间是符合题目要求的区间。所以

当区间不满足题目要求的时候，我们就使区间 r++ ，吸纳更多的元素，这样就可以让区间符合题目的要求。
当区间已经符合了题目的要求后，我们就让区间 l++ ，减少元素，尽量让区间变得更小，直到区间不再满足题目要求为止。

这个就是这个算法的基本思想，接下来我们带入到题目当中去计算。

其实这类题目的代码较为模板，主要就是要寻找到其区间知否满足题目要求的要点。

我们先准备一个 l 和 r ，由于在循环中 r 还需要 ++ ，所以先赋值为 0。

cpp
int l = 1, r = 0;

接下来就要进入循环的环节。循环的判断值就是这个区间走向了尽头，也就是说 r 在下一步的时候会超出 $N$ 的界限。判断如下：r + 1 <= n

我们先讨论前面的「当区间不符合题目要求」的这种情况，我们就让 r 按照惯例往后推一个，然后记录这个数字。如果这是一个新的数字，我们就让 cnt++ ，来记录区间里面不同的数的个数。

cpp
r++;
t[a[r]]++;
if (t[a[r]] == 1) {
    cnt++;
}

然后，我们来讨论「符合题目要求」的情况。判断条件为 cnt == m 当满足这个情况的时候，我们要先尽量的「紧区间」，也就是把臃肿的部分去掉。

如果去掉这个并不会影响不同的数的个数，也就是在这个区间内还有这个数的话，而且 l 没有超过 r ，则这个数可以去掉。浴室就产生了这个循环。

cpp
while (l + 1 <= r && t[a[l]] != 1) {
    t[a[l]]--;
    l++;
}

最后记录一下最小值，为基本内容，不做讲述。

cpp
if (r - l + 1 < minn) {
    mina = l;
    minb = r;
    minn = r - l + 1;
}

把上述模块组合在一起，就是如下AC代码。

cpp
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000
int a[maxn + 10];
int t[2000 + 10];
int cnt = 0;
int minn = maxn + 10;
int mina, minb;
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = 0;
    while (r + 1 <= n) {
        r++;
        t[a[r]]++;
        if (t[a[r]] == 1) {
            cnt++;
        }
        if (cnt == m) {
            while (l + 1 <= r && t[a[l]] != 1) {
                t[a[l]]--;
                l++;
            }
            if (r - l + 1 < minn) {
                mina = l;
                minb = r;
                minn = r - l + 1;
            }
        }
    }
    cout << mina << " " << minb;
    return 0;
}

P1115 最大子段和

题目的主要意思非常的清楚，求所以连续非空区间的和的最大值。

这个有点类似于滑动窗口，但是差别非常的大，我们就样例分析。

txt
7
2 -4 3 -1 2 -4 3

选中第一个数字 2 后。后面的数字是 -4 。如果 -4 在这个答案区间里，那么 2 肯定也在，因为可以增加区间的和。

选中第二个数字 -4 后，后面的数字是 3 。这个时候就必须舍弃掉 2 和 -4 了，因为他们的和事 -2 ，对于3 没有任何好处。

选中第三个数字 3 并且舍弃掉前面的数字后，和变成了3 。这个时候 -1 肯定要 3 ，因为有助于区间和的增加。

后面的数字以此类推。

这个时候我们就可以分析出来算法了。如果前面的窗口加上这个数不如这个数本身大的时候，也就是前面的窗口是负数的时候，我们就可以舍弃掉这一段，从新开始计数。

下面开始着手写代码。

首先我们默认区间选中了第一个数，也就是有如下代码

cpp
int maxx = a[1];
int cnt = a[1];

在循环当中，如上所说，当前的窗口的和为如下选择：

如果当前的和为负数，也就是加上这个数比这个数本身小的时候，我们就从新开始窗口，当前的数是新窗口的第一个数，窗口的和是这个数
如果当前的和为正数，也就是加上这个数比这个数本身大的时候，我们就延续这个窗口，和加上这个数。

最后取最大值。

于是就有了如下代码

cpp
for (int i = 2; i <= n; i++) {
    cnt = max(a[i], cnt + a[i]);
    maxx = max(maxx, cnt);
}

上面就是核心代码的解析，这个是所有的代码

cpp
#include <bits/stdc++.h>
using namespace std;
int a[200000 + 10];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int maxx = a[1];
    int cnt = a[1];
    for (int i = 2; i <= n; i++) {
        cnt = max(a[i], cnt + a[i]);
        maxx = max(maxx, cnt);
    }
    cout << maxx;
    return 0;
}

P7072 [CSP-J2020] 直播获奖

这个题目的大致意思就是按照一系列算法，求出实时得奖人数，并且从大到小得出的奖分数线。

这个题目的难点在于，我们要绕过常规思维——每次输入一个数都要重新排序。

这里先介绍一个非常常见的优化方法——「桶排序」

这个算法的方式就是准备一个数组，数组的大小就是所有要处理的数的最大值。

便利所有的数，将数的值作为下标的元素加一。换成公式就是这样的。 $t[A_i]++$

然后从最大值便利到最小值，输出。我们设定最大值是 maxx 那么遍历代码如下

cpp
for (int i = maxx; i >= 0; i--) {
    for (int j = 1; j <= t[i]; j++) {
        cout << i << " ";
    }
}

这个就是「桶排序」的基本思想。与用到这题上面，我们就可以输入一个数后将其装入桶，每次再从大到小便利，由于每个数的数据范围不大，所有这道题目就引刃而解了。

首先先输入并且装桶。

cpp
int a;
cin >> a;
t[a]++;

然后根据题目里面的内容计算现在的「计划获奖人数」

cpp
int people = 1;
people = max(people, i *w / 100);

然后再想上文一样，从大到小便利，每次计算当前学生总数，超过或者到达「计划获奖人数」后停止，然后输出。

cpp
int cnt = 0;
for (int j = 600; j >= 0; j--) {
    cnt += t[j];
    if (cnt >= people) {
        printf("%d ", j);
        break;
    }
}

这就是核心部分，其它的部分就是一些输入输出等非重点，可以自行查看代码。

cpp
#include <bits/stdc++.h>
using namespace std;
int t[1000];
int main() {
    int n, w;
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        t[a]++;
        int people = 1;
        people = max(people, i * w / 100);
        int cnt = 0;
        for (int j = 600; j >= 0; j--) {
            cnt += t[j];
            if (cnt >= people) {
                printf("%d ", j);
                break;
            }
        }
    }
    return 0;
}

注意

这篇文章还没有结束，但是由于篇幅预估会很长，写作时间跨度大，所以先发布。

目录

P1102 A-B 数对

P1638 逛画展

P1115 最大子段和

P7072 [CSP-J2020] 直播获奖