秋招突击——6/25——复习{单调队列优化——最大子序列和，单调队列优化——修剪草坪}—

秋招突击——6/25——复习{单调队列优化——最大子序列和，单调队列优化——修剪草坪}——新作{搜索插入位置}

文章目录

- 引言
- 复习
- - 单调队列优化——最大子序列和
  - - 个人实现
  - 单调队列优化——修建草坪
  - - 个人实现
    - 参考实现
- 新作
- - 搜搜插入位置
  - - 个人实现
    - 参考实现
- 总结

引言

明天要去上海了，今天要打印很多东西，准备很多材料，包括请假，所以上午没有时间刷题和背书，这是侵占了我下午的时间做的。
今天时间不能占据太久，主要做一下单调队列优化的题目，之前就做过一个。

复习

还是换一下思路吧，今天还是就做一种类型的题目，把单调队列优化做了，总共是两道题，一个旧的题目——最大子序列和以及一个新的题目——修建草坪。
单调队列是后来做的，学的并不多，但是那道题我推导了很久，这里放一下对应的连接。

单调队列优化——最大子序列和

上一次分析做题的链接。
最大子序列和
有以下几个注意点
- 子序列和的问题，所以需要预先处理并保存所有样本的子序列和
- 有一个子序列限制，需要保证单调子序列的范围在m之内
如果使用动态规划，其实就是计算不同情况下的最优值，知道状态转移方程怎么计算。感觉这种题，和动态规划的关系并不大。

个人实现

#include <iostream>
#include <limits.h>
using namespace std;

typedef long long LL;
const int N = 300010;
LL s[N],q[N];// s表示前序和，q表示单调队列的维护
int n,k;

int main(){
    cin>>n>>k;

    // 计算前n项和
    for (int i = 1; i <= n; ++i) {
        cin>>s[i];
        s[i] += s[i - 1];
    }

    // 计算前n项队列
    int ll = 0,tt = 0;
    LL res = INT_MIN;
    q[0] = 0;  // 补充
    for (int i = 0; i <= n; ++i) {
        // 遍历这个序列的终点
        // 保证单调队列的起点和i的范围实在k以内的
        if (i - q[ll] >= k && tt >= ll)    ll ++;
        // 移动和单调递增队列中的相关值后，比较以下最小值的情况下，是否满足最终结果
        res = max(res,s[i] - s[q[ll]]);
        // 维系单调递增队列末尾元素，保证记录的都是最小的元素
        while(tt >= ll && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
    }
    cout<<res;
}

大概复习了一下，虽然知道了怎么维系单调队列，但是有以下几个细节没有注意到，分别是
- 在每一次更新ll和tt之前，都没有对结果进行判定，保证右节点和左节点的相对关系
- 没有初始化q[0]的值，这里面res应该是最小值才行，因为的最终的结果有可能是负数。

单调队列优化——修建草坪

在这里插入图片描述

重点关注

N的上确界是10的五次方，还有Ei的上确界是10的9次方，注意使用数据存储的方式的。
不能包含超过K只编号连续的奶牛，有N只奶牛，然后有K只奶牛是不能出现连号的。保证效率最高。==》连号最多的是K个，选择最多个小于或者等于K的子序列，然后进行输出。

个人实现

我这里会对问题进行拆解，那就是假设只能选一次，我现在要选一个长度小于等于K的，累加和最大的子序列，这个很好做。
- 现在是要选出尽可能多的子序列，然后在进行匹配？但是子序列和子序列之间应该如何进行选择？这又是一个问题。
若干个子序列之间应该如何选择共存？如何相互影响？
- 想不出来，状态转换机？具体应该怎么做？拆成若干个字段，然后进行匹配应该是可以的吧！这个可以尝试一下。这边选出一个最长字串之后，然后在递归调用，然后再分割，在选择最长字串，这样应该可以做了。

大概就这样了，能不能跑起来就不看了，大概思路实现如下

#include <iostream>
#include <limits.h>
using namespace std;

typedef long long LL;
const int N = 10010;
LL s[N];// s表示前序和，q表示单调队列的维护
int n,k;
LL res = 0;

void subStr(int ll,int rr){
    if (ll > rr)    return;
    LL q[N];
    q[0] = 0;
    int hh = 0, tt = 0;
    LL tRes = 0;
    int lhh,rtt;
    for (int i = ll; i <= rr; ++i) {
        if(tt >= hh && i - q[hh] > k) hh ++;
        if (tRes < s[i] - s[q[hh]]){
            tRes = s[i] - s[q[hh]];
            lhh = q[hh];
            rtt = i;
        }
        while(tt >= hh && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
    }
    res += tRes;
    subStr(ll,lhh - 1);
    subStr(rtt + 1,rr);
}

int main(){
    cin>>n>>k;

    // 计算前n项和
    for (int i = 1; i <= n; ++i) {
        cin>>s[i];
        s[i] += s[i - 1];
    }
    subStr(1,n);
    cout<<res<<endl;
}

参考实现

这道题他的思路和我的不一样，有一个很关键的地方，使用了一个等式进行转换，我的方法应该有问题，我从最优地开始选择，最终并不一定是最优的，所以还是得好好看看他的代码。
具体推导思路如下

请添加图片描述

本质上，就是计算了针对g(i)的单调递减队列，找一个g(j)这个范围内的最大值，最大值，然后在进行计算的。
感觉这个单调队列，理解起来还是有点问题，上一道题的理解是到位了，推导过了，这一道题，就有点问题了。
想了一下，又陷入一个问题中，**注意！！**这里是前j项累加和最大，不是单个项。然后，就是再k个窗口之内，计算g(i)的最大值，保存一下单调递减队列就行了，时间有限，这里就不自己写了，直接贴上y总的代码吧

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N];
LL f[N];
int q[N];

// 公式转换的精髓。
LL g(int i)
{
    if (!i) return 0;
    return f[i - 1] - s[i];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - m) hh ++ ;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while (hh <= tt && g(q[tt]) <= g(i)) tt -- ;  // 维护一个单调递减队列，保证队首的一定是最大值，这里已经维护到i的一个单调递减队列，已经是没有任何毛病的，hh是单调递减队列的头部。
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/128401/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

新作

搜搜插入位置

今天本来是一道困难的题目，但是因为要早睡，明天早上五点半要起床赶飞机，所以找了一道简单的题目，重新做一下。
题目链接

个人实现

二分查找，然后返回l

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int searchInsert(vector<int>& nums, int t) {
    int l = 0 , r = nums.size() - 1;
    int mid = 0;
    while(l <= r){
        mid = (l + r) / 2;
        if (nums[mid] == t)     return mid;
        else if(nums[mid] < t){
            l = mid + 1;
        }else if(nums[mid] > t){
            r = mid - 1;
        }
    }
    return l;
}

在这里插入图片描述

参考实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/search-insert-position/solutions/333632/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

学习