首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

双指针优化

编程知识
2024年08月08日 10:44

双指针优化

为什么我为OI泪目?因为我菜得离谱......

引入

双指针是一种简单而又灵活的技巧和思想,单独使用可以轻松解决一些特定问题,和其他算法结合也能发挥多样的用处。
双指针顾名思义,就是同时使用两个指针,在序列、链表结构上指向的是位置,在树、图结构中指向的是节点,通过或同向移动,或相向移动来维护、统计信息。 --摘自OI wiki

说白了,双指针是类似贪心的一种维护区间的算法,在有单调性的区间问题中战力爆表,还可以解决链表判环的问题。
接下来让蒟蒻来解释。

题目

连续自然数和 P1147橙-传送门

题目描述

对一个给定的正整数 M,求出所有的连续的正整数段(每一段至少有两个数),这些连续的自然数段中的全部数之和为 M。

例子:1998+1999+2000+2001+2002 = 10000,所以从 1998 到 2002 的一个自然数段为 M=10000 的一个解。

输入格式

包含一个整数的单独一行给出 M 的值(10 <= M <= 2,000,000)。

输出格式

每行两个正整数,给出一个满足条件的连续正整数段中的第一个数和最后一个数,两数之间用一个空格隔开,所有输出行的第一个按从小到大的升序排列,对于给定的输入数据,保证至少有一个解。

样例 #1

样例输入 #1
10000
样例输出 #1
18 142 
297 328 
388 412 
1998 2002

解析

显而易见,这道题是要我们找出一个和为Mi~j自然数的区间,但这个区间很大,暴力枚举ij的复杂度高达 n^2所以只能另外想办法(虽然n^2也能过,这道题数据太water
我们先来看数据较小的样例
1 2 3 4 5 6 7 M==12 令S为该i~j区间的和
我们令i指向[1],j指向[0],其中i表示左端,并取这个值(a[i]),j表示右端,并取这个值(a[j])。
如果得出的S<M 例如i=1,j=1的时刻就令j++,右端点+1S也扩大,
如果得出的S>=M 例如i=1,j=5的时刻 就令i++,左端点+1S缩小,
这样答案就能逐渐逼近正解 所以说与贪心类似
如果得出的S==M 例如i=3,j=5的时刻 就输出答案左右端点,此时不要忘了将i++j++,以准备更新下一个解。
j>n时,就可以OK结束循环了。
你学废︿( ̄︶ ̄)︿了吗?
后面的解析会很简略~~~~~~~~~~~

CODE

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif
    long long m;
    cin>>m;
    __int128 tans=0;
    int i=1,j=0;while(1)//[i,j]
    {
        if(i>m/2) return 0;
        if(tans>m) tans-=i,i++;
        if(tans<m) j++,tans+=j;
        if(tans==m) cout<<i<<" "<<j<<endl,tans-=i,i++;
    }
    return 0;
}


逛画展 P1638黄-传送门

题目描述

博览馆正在展出由世上最佳的 m 位画家所画的图画。

游客在购买门票时必须说明两个数字,a 和 b,代表他要看展览中的第 a 幅至第 b 幅画(包含 a,b)之间的所有图画,而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然,他想最小化购买门票的价格。

请求出他购买门票时应选择的 a,b,数据保证一定有解。

若存在多组解,输出 a 最小的那组

输入格式

第一行两个整数 n,m,分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 n 个整数 a_i,代表画第 i 幅画的名师的编号。

输出格式

一行两个整数 a,b。

样例 #1

样例输入 #1
12 5
2 5 3 1 3 2 4 1 1 5 4 3
样例输出 #1
2 7

提示

数据规模与约定
  • 对于 30% 的数据,有 n<=200,m<=20。
  • 对于 60% 的数据,有 n<=10^5, m<=10^3 。
  • 对于 100% 的数据,有 1<=q n<=10^6,1 <=q a_i <=q m<=2*10^3。

题解

i j 维护左右区间,用一个tong[]数组桶计算,用一个int alls来维护现在的桶内元素,add:元素添加era:元素删除
i=1,j=0,接下来看i指向的元素是否有重复,如果有重复就右移左端点 i++,舍弃a[i]这个元素,否则左移动右端点 j++,增加a[j]这个元素,
如果当前区间符合alls==m,则将其加入vector<pair<int,int>> ans答案数组中,
最后扫描ans,得出最佳答案即可。

CODE

#pragma
#include<bits/stdc++.h>
// #include<windows.h>
using namespace std;
const int tsn=1e6+5;
const int tstong=1e3+5;
int a[tsn];
int tong[tstong],alls=0;
vector<pair<int,int> >ans;
void add(int k)
{
    alls+=(!tong[k]),tong[k]++;
}
void era(int k)
{
    if(tong[k]==1) alls--;
    if(tong[k]) tong[k]--;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);freopen("00out.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int mi=1,mj=0;while(mj<=n+1)
    {
       
        if(alls==m) ans.push_back({mi,mj});
        if(tong[a[mi]]>=2) era(a[mi]),mi++;
        else mj++,add(a[mj]);//记得更新端点,add(a[mj])!
    }
    pair<int,int>lans={tsn,INT_MAX};
    for(int i=0;i<ans.size();i++)
    {
        if((ans[i].second-ans[i].first)<(lans.second-lans.first)) lans=ans[i];
        if((ans[i].second-ans[i].first)==(lans.second-lans.first)&&ans[i].first<lans.first) lans=ans[i]; 
    }
    cout<<lans.first<<" "<<lans.second<<endl;
    return 0;
}


[蓝桥杯 2020 省 A1] 整数小拼接 P8708黄-传送门

题目描述

给定一个长度为 n 的数组 A_1,A_2,...,A_n。你可以从中选出两个数 A_i 和 A_j(i!= j),然后将 A_i 和 A_j 一前一后拼成一个新的整数。例如 12345 可以拼成 1234534512。注意交换 A_i 和 A_j 的顺序总是被视为 2 种拼法,即便是 A_i=A_j 时。

请你计算有多少种拼法满足拼出的整数小于等于 K。

输入格式

第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A_1,A_2,...,A_n。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1
4 33
1 2 3 4
样例输出 #1
8

提示

对于 30% 的评测用例 1<= n<=1000,1<= k<=10^8,1<= A_i<=10^4。

对于所有评测用例,1<= n<=10^5,1<= k<=10^{10},1<= A_i<=10^9。

蓝桥杯 2020 第一轮省赛 A 组 H 题。

题解

请自己思考,不行去LUOGU翻
西江月·证明
即得易见平凡,仿照上例显然。
留作习题答案略,读者自证不难。
反之亦然同理,推论自然成立,略去过程QED,由上可知证毕。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int tsn=1e6+5;
long long a[tsn];
long long n,k;
int X(int a,int b)
{
    if(b==0) return 0;
    int wei=0;
    int kb=b;
    while(b) b/=10,wei++;
    long long ans=a*(pow(10,wei)/1)+kb;
    if(ans>k) return 0;
    return 1;
}
vector<pair<int,int> >v;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif
    cin>>n>>k;
    long long lans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    // for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
    int i=1,j=n;while(j>0&&i<=n)
    {
        if(X(a[i],a[j])) v.push_back({i,j}),i++;
        else j--;
    }
    for(int x=0;x<v.size();x++)
    {
        if(v[x].second>=v[x].first) lans+=v[x].second-1;
        else lans+=v[x].second;
    //特别注意边界范围!
        // cout<<v[x].first<<" "<<v[x].second<<endl;
    }
    cout<<lans;
    return 0;
}


[USACO11NOV] Cow Lineup S P3209黄-传送门

题面翻译

问题描述

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种,他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方, 每一头牛由一个整数位置 X_i以及整数品种编号 ID_i表示。

约翰想拍一张照片,这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当,这就意味着,在一

系列照片中的最大和最小 X坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本,这些照片中有每个不同的品种的至少一头牛,没有两头牛愿意站

在同一个地点的。

输入格式

第 1行:牛的数量 N;

第 2..1+N行:每行包含 2 个以空格分隔的正整数 X_i和 ID_i;意义如题目描述;

输出格式

输出共一行,包含每个不同品种 \rm ID的照片的最低成本。

题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

输入格式

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion (也就是1e10).

输出格式

* Line 1: The smallest cost of a photograph containing each distinct breed ID.

样例 #1

样例输入 #1
6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1
样例输出 #1
4

提示

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.

题解

请自己思考,不行去LUOGU翻
西江月·证明
即得易见平凡,仿照上例显然。
留作习题答案略,读者自证不难。
反之亦然同理,推论自然成立,略去过程QED,由上可知证毕。

CODE

#pragma
#include<bits/stdc++.h>
using namespace std;
const int tsn=5e5+5;
#define int long long
pair<int,int>a[tsn]={{0,0}};//first->where second->id
map<int,int>tong;
int alls=0;
int n;
int lans=INT_MAX;
void add(int k)
{
    if(tong[k]==0) alls++;
    tong[k]++;
}
void era(int k)
{
    if(tong[k]==1) alls--;
    if(tong[k]) tong[k]--;
}
int get_K()
{
    for(int i=1;i<=n;i++) add(a[i].second);
    int getk=alls;alls=0;tong.clear();
    return getk;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("00in.txt","r",stdin);
        freopen("00out.txt","w",stdout);
    #endif

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    int K=get_K();
    // for(int i=1;i<=n;i++) cout<<"a:"<<a[i].first<<" "<<a[i].second<<endl;
    int i=1,j=0;while(j<=n)
    {
        // cout<<i<<" "<<j<<endl;
        if(alls==K)
        {
            int tans=a[j].first-a[i].first;
            if(tans<lans) lans=tans;
            j++,add(a[j].second);//注意好了,这里一定要有添加操作!
        }
        if(tong[a[i].second]>=2) era(a[i].second),i++;
        else j++,add(a[j].second);
    }
    cout<<lans;
    return 0;
}


完结撒花!

image
image

From:https://www.cnblogs.com/happy-salted-fish/p/18348643
本文地址: http://www.shuzixingkong.net/article/907
0评论
提交 加载更多评论
其他文章 总有坏人想爬我网站的数据,看我用这 10 招干他!
大家好,我是程序员鱼皮。前两天模拟面试一位社招两年的老哥,由于他的表现不错,我就临时起意,跟他交流一下我们最近遇到的业务场景问题。问题如下: 最近我们不是做了个 程序员刷题网站 - 面试鸭 嘛,有很多坏人盯上了我们网站,想把我们 4,000 多道面试题、100 多个面试题库的数据都用爬虫抓下来。那我
总有坏人想爬我网站的数据,看我用这 10 招干他! 总有坏人想爬我网站的数据,看我用这 10 招干他! 总有坏人想爬我网站的数据,看我用这 10 招干他!
零基础学习人工智能—Python—Pytorch学习(二)
前言 数学的学习跟数学的计算是要分开的,现在回头再去看大学的高数和线性代数,如果只是学习的话,其实一门课程3天,也就学完了。 学校的课程之所以上那么久,其实是为了考试,也就是为计算准备的。计算有意义的,在有计算机的情况下,计算的意义并不是很大。 所以,如果大学数学没学好,只要花一星期,就能补回来。甚
零基础学习人工智能—Python—Pytorch学习(二) 零基础学习人工智能—Python—Pytorch学习(二) 零基础学习人工智能—Python—Pytorch学习(二)
记一次 .NET某智慧出行系统 CPU爆高分析
一:背景 1. 讲故事 前些天有位朋友找到我,说他们的系统出现了CPU 100%的情况,让我帮忙看一下怎么回事?dump也拿到了,本想着这种情况让他多抓几个,既然有了就拿现有的分析吧。 二:WinDbg 分析 1. 为什么会爆高 既然说是 100%,作为调试者得拿数据说话,可以使用 !tp 来观测一
记一次 .NET某智慧出行系统 CPU爆高分析 记一次 .NET某智慧出行系统 CPU爆高分析 记一次 .NET某智慧出行系统 CPU爆高分析
MySQL 5.7 DDL 与 GH-OST 对比分析
本文首先介绍MySQL5.7 DDL以及GH-OST的原理,然后从效率、空间占用、锁阻塞、binlog日志产生量、主备延时等方面,对比GH-OST和MySQL5.7 DDL的差异。
MySQL 5.7 DDL 与 GH-OST 对比分析 MySQL 5.7 DDL 与 GH-OST 对比分析 MySQL 5.7 DDL 与 GH-OST 对比分析
[rCore学习笔记 023]任务切换
导读 还是要先看官方手册. 学过DMA的同志可能比较好理解,一句话, 释放CPU总线 : 如果把应用程序执行的整个过程进行进一步分析,可以看到,当程序访问 I/O 外设或睡眠时,其实是不需要占用处理器的,于是我们可以把应用程序在不同时间段的执行过程分为两类,占用处理器执行有效任务的计算阶段和不必占用
[rCore学习笔记 023]任务切换 [rCore学习笔记 023]任务切换 [rCore学习笔记 023]任务切换
前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化
这一章主要分享一下使用 Konva 遇到的性能优化问题,并且介绍一下 UI 美化的思路,主要使用 Naive UI。
前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化 前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化
前后端分离项目,后期前端身份验证的麻烦
软件构成 后端 后端是一个asp.netcore webapi项目,使用jwt进行身份验证和鉴权。 前端 前端是一个基于http协议的asp.netcore RezorPage项目,但实际上完全使用的wwwwroot目录下的静态文件。没有使用RazorPage。 目前只有后端接口鉴权,前端页面任意访
前后端分离项目,后期前端身份验证的麻烦 前后端分离项目,后期前端身份验证的麻烦
vue前端自适应布局,一步到位所有自适应
1,左右布局 - 左侧固定宽带,右侧自适应剩余的宽度。 - 中间一条分割线,可以拖拉,自适应调整左右侧的宽度。 - 左侧的高度超长自动出现横向滚动条,左侧宽度超长,自动出现竖向滚动条。 2,上中下布局 - 最上面的 搜索条件 div 固定占用 100 px 高度,下面的 查询条件 div 固定
vue前端自适应布局,一步到位所有自适应 vue前端自适应布局,一步到位所有自适应