Peter算法小课堂—简单建模(4)

2023-12-18 21:52

本文主要是介绍Peter算法小课堂—简单建模(4),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

太戈编程1655题

一条直线上,你安排了n个哨兵站岗放哨,编号从1到n。其中i号哨兵的坐标位置是x[i]。不会有哨兵站在相同的位置。作为指挥官,你需要知道3个信息:

1.从左到右,每个哨兵的坐标依次是几?

2.从左到右,每个哨兵依次是几号哨兵?

3.哨兵编号从1到n,每个哨兵依次站在从左到右的第几个?

离散化

什么是离散化呢?数据离散化处理_哔哩哔哩_bilibili

给出一列数字,在有些情况下,这些数字的值的绝对大小并不重要,而相对大小很重要。例如,对一个班级学生的成绩进行排名,此时不关心成绩的绝对值,只需要输出排名,如分数为{95,50,72,21},排名为{1,3,2,4}。

“离散化”就是用数字的相对值替代它们的绝对值。离散化是一种数据处理的技巧,它把分布广而稀疏的数据转换为密集分布,从而能让算法更快速、更省空间的处理。步骤:1.排序 2.离散化 3.归位

离散化手工编码:

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
struct data{int val;int id;
}olda[N];
int newa[N];
bool cmp(data x,data y){return x.val<y.val;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>olda[i].val;olda[i].id=i;}sort(olda+1,olda+1+n,cmp);for(int i=1;i<=n;i++){newa[olda[i].id]=i;}for(int i=1;i<=n;i++) cout<<newa[i];return 0;
}

那么,回到1655,这题应该怎么做呢?

#include <bits/stdc++.h>
using namespace std;
const int N=100009;
int rk[N];
struct guard{//结构体int x,id;
};
guard g[N];
bool cmp(const guard&u,const guard&v){//排序return u.x<v.x;
}
int main()
{freopen("guard.in","r",stdin);freopen("guard.out","w",stdout);int n;cin>>n;	 for(int i=1;i<=n;i++) cin>>g[i].x;for(int i=1;i<=n;i++) g[i].id=i;//学号赋值sort(g+1,g+1+n,cmp);for(int i=1;i<=n;i++) rk[g[i].id]=i;for(int i=1;i<=n-1;i++) cout<<g[i].x<<" ";cout<<g[n].x<<endl;    for(int i=1;i<=n-1;i++) cout<<g[i].id<<" ";cout<<g[n].id<<endl;    for(int i=1;i<=n-1;i++) cout<<rk[i]<<" ";    cout<<rk[n]<<endl;return 0;
}

太戈编程56题

某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树

差分

cin>>l>>m;
for(int i=1;i<=m;i++){cin>>a>>b;if(a>b) swap(a,b);a++;b++;//确保都为正整数d[a]++;d[b+1]--;
}

 那么,第5行我为什么敢无缘无故+1呢?这都是缓冲格的帮助。

然后呢?

#include <bits/stdc++.h>
using namespace std;
const int N=1000009;
int l,m,a,b,s[N],d[N];
int main(){freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);cin>>l>>m;for(int i=1;i<=m;i++){cin>>a>>b;if(a>b) swap(a,b);a++;b++;d[a]++;d[b+1]--;}int ans=l+1;for(int i=1;i<=l+1;i++){s[i]=s[i-1]+d[i];if(s[i]) ans--;}cout<<ans<<endl;return 0;
}

但是……如果303题怎么办呢?

太戈编程303题

#include <bits/stdc++.h>
using namespace std;
const int M=1000000009;
struct pnt{int x,tag;
}p[M];
bool cmp(const int&a,const int&b){if(p[a].x<p[b].x) return 1;if(p[a].x>p[b].x) return 0;if(p[a].tag<p[b].tag) return 1;return 0;
}
int main(){int l,m;cin>>l>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;if(a>b) swap(a,b);a++;b++;p[i].x=a;p[i].tag=1;p[i+m].x=b+1;p[i+m].tag=-1;}for(int i=1;i<=2*m;i++) id[i]=i;sort(id+1,id+1+2*m,cmp);int ans=l+1,pre=0;for(int i=1;i<=2*m;i++){if(s[i-1]) ans-=p[id[i]].x-pre;pre=p[id[i]].x;s[i]=s[i-1]+p[id[i]].tag;}cout<<ans<<endl;
}

希望这些对大家有用,三连必回

这篇关于Peter算法小课堂—简单建模(4)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/509882

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

基于Python实现一个简单的题库与在线考试系统

《基于Python实现一个简单的题库与在线考试系统》在当今信息化教育时代,在线学习与考试系统已成为教育技术领域的重要组成部分,本文就来介绍一下如何使用Python和PyQt5框架开发一个名为白泽题库系... 目录概述功能特点界面展示系统架构设计类结构图Excel题库填写格式模板题库题目填写格式表核心数据结构

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》:本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要