Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法手记3

算法手记3

作者头像
修修修也
发布于 2025-03-14 01:36:28
发布于 2025-03-14 01:36:28
10300
代码可运行
举报
运行总次数:0
代码可运行

一.dd爱框框

牛客网题目链接(点击即可跳转):dd爱框框

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 滑动窗口!双指针一个left,一个right,同向向后滑动即可.窗口大于x就缩紧left向后移动,窗口小于x就扩大right向后移动.注意,left的下标从0开始,输出位置时要加1,right表示的是和left的相对距离,所以输出时不用加1.思路图示如下:


解题代码:

本题解题代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<iostream>
#include<vector>

using namespace std;
int main()
{
    //滑动窗口,同向双指针
    //输入数据
    int n,x;
    cin>>n>>x;
    vector<int> vi;
    vi.resize(n);
    for(int i=0;i<n;i++)
    {
        cin>>vi[i];
    }
    //开始解题
    int left=0,right=0;
    int min_left=0,min_right= n;
    int sum=0;
    while(left<n && right<n && left<=right)
    {
        if(sum<x)
        {
            //扩大窗口
            sum+=vi[right];
            right++;
        }
        else
        {
            //如果新窗口长度比老窗口小,就更新最小区间
            if((right-left) < (min_right-min_left))
            {
                min_right=right;
                min_left=left;
            }
            //缩小窗口
            sum-=vi[left];
            left++;
        }
    }
    
    cout<<min_left+1<<" "<<min_right;
    return 0;
}

二.除2!

牛客网题目链接(点击即可跳转):除2!

题目详情:

本题详情如下图:


题目思路:

本题解题思路如下: 一开始输入的时候把奇数直接加到sum里,偶数直接push进大根堆,后面循环k次(条件是堆不为空)把堆顶的数据除2,堆顶除2后还是偶数就继续push进堆,如果不是偶数就直接加进sum.循环完毕把堆里剩下的偶数加进sum后输出即可.

解题代码:

本题解题代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<iostream>
#include<queue>
using namespace std;

int main()
{
    int n,k,tmp;
    long long sum;
    cin>>n>>k;
    priority_queue<int> pq;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        if(tmp%2==0)
            pq.push(tmp);
        else
            sum+=tmp;
    }
    for(int i=0;i<k;i++)
    {
        if(pq.empty())
            break;
        tmp = pq.top()/2;
        pq.pop();
        if(tmp%2==0)
            pq.push(tmp);
        else
            sum+=tmp;
    }
    while(!pq.empty())
    {
        sum+=pq.top();
        pq.pop();
    }
    cout<<sum;
    return 0;
}

结语

说点啥好呢...这两道题都不难,主要是手生,一时半会就ac不出来,有思路可以,下次画个图可能会更直观明了一点.以及之前手撕的STL没想到还有漏网之鱼,后续有空记得补一篇优先级队列的使用说明手册哈.

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-03-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【C++】 —— 笔试刷题day_3
这里我们可以看到输入的复合词中,每一个单词用 隔开;所以我们就可以应该单词应该单词读取(而不是使用getline来读取一行)。
星辰与你
2025/03/13
820
【C++】 —— 笔试刷题day_3
poj-3253 优先队列
该文章介绍了如何利用优先队列求解一道题目,并总结了一些解题思路。
用户1148523
2018/01/09
6580
ny55 懒省事的小明
时间限制: 3000 ms  |            内存限制: 65535 KB
全栈程序员站长
2021/12/23
3070
算法与数据结构之优先级队列
复习一下:前面讲的最大最小堆的生成,是把一个数组转换成完全二叉树之后,才转换成最大最小堆的。然后生成的时候先从最下方的叶结点开始生成最大/最小堆。
灯珑LoGin
2022/10/31
2830
算法与数据结构之优先级队列
LeetCode 221场周赛题解
【GiantPandaCV导语】这是LeetCode的第221场周赛的题解,本期考察的知识点有模拟,贪心,优先队列,01Trie树等。
BBuf
2021/01/08
3480
Topk算法_topn算法
思路1:快速选择算法 可以采用快速选择算法,借助快排,设mid为每次划分中间结果,每次划分完之后如果mid==k,则说明序列刚刚好,第k位置和他前面的位置都是前K大的数,如果mid < k,则说明第K大的元素在后半部分,则前半部分肯定是前K大的数,只需从后半部分找k – mid大的数即可,否则如果mid > k,则说明第K大的数在前半部分,只需从前半部分找前K大的数字即可。 时间复杂度:假设每次划分的mid都在中间,每层都只是对一半做划分,所以每次划分的数据量为 n,n/2,n/4,n/8…一共有logn层,根据等比数列可以算出来时间复杂度为O(n) C++代码演示
全栈程序员站长
2022/09/21
4530
一次讲透次短路及条数问题,详细探讨dijkstra算法的本质
继续学习次短路~ hdu 3191 How Many Paths Are There
ACM算法日常
2019/11/06
1.8K0
一次讲透次短路及条数问题,详细探讨dijkstra算法的本质
第k短路径_典型的分类算法K均值
给定一张 N 个点(编号 1,2…N),M 条边的有向图,求从起点 S 到终点 T 的第 K 短路的长度,路径允许重复经过点或边。
全栈程序员站长
2022/09/22
3600
蓝桥杯 基础练习 Huffuman树
  Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。   给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:   1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。   2. 重复步骤1,直到{pi}中只剩下一个数。   在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。   本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。
Meng小羽
2019/12/23
3760
【C++】优先级队列以及仿函数
在C++中优先级队列的相关接口就是如上这些。这里的top,如果大的值优先级高,也就是大堆,top返回的就是堆里面的最大值,如果是小的数优先级高,也就是小堆,返回的就是最小值。
羚羊角
2024/12/29
1620
【C++】优先级队列以及仿函数
【蓝桥杯】BASIC-28 Huffman树
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
喜欢ctrl的cxk
2019/11/13
6300
比赛名次
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
喜欢ctrl的cxk
2019/11/08
5210
程序员进阶之算法练习(四十三)
题目链接 题目大意: 屏幕上有a*b个像素点,其中第(x、y)个像素点已经损坏;(x和y从0开始) 现在想在屏幕上选出一个矩形,这个矩形的边与屏幕的边缘平行,并且不包括损坏的像素点(x,y); 问这个矩形的最大面积是多少?
落影
2020/05/26
3070
新鲜出炉的阿里、虾皮和网易笔试题解
9.18 日网易笔试在牛客上闹出大瓜,笔试还没结束的时候候选人在牛客评论区公然交流代码,事后牛客工作人员获取了后台记录,并上报给了网易,直接取消了 50 余人的校招资格
ACM算法日常
2021/09/28
1.3K0
喊山第二部_demjanov重排
喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html)
全栈程序员站长
2022/09/22
3010
【优先级队列】最后一块石头的重量 && 数据流中的第 K 大元素
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
利刃大大
2025/03/15
1230
单源最短路径dijkstra算法_tous les jours蛋糕
酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要 8000 金币。如果你能够弄来他的水晶球,那么只要 5000 金币就行了。”
全栈程序员站长
2022/09/22
2840
数据结构 Huffman树
Huffman 介绍 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点
Kindear
2017/12/29
1.5K0
数据结构 Huffman树
C++ STL之priority_queue
    STL中的priority_queue(优先队列)是一种会按照自定义的一种方式(数据的优先级)来对队列中的数据进行动态的排序的容器,不同优先级的情况下,top()上永远是最高优先级的数据,其底层采用的是堆结构(默认大顶堆)。注意相同优先级下并没有先进先出,后面的例子中可以看到    头文件#include<queue>    标准库默认使用元素类型的<操作符来确定它们之间的优先级关系,数据越大优先级越高,想要改变优先级的界定方式的话需要重载<操作符。    先看个最简单的: #include<ios
用户1215536
2018/02/05
1.1K0
【Codeforces】1219D - Workout plan
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
喜欢ctrl的cxk
2019/11/08
4130
【Codeforces】1219D - Workout plan
相关推荐
【C++】 —— 笔试刷题day_3
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档