秒懂算法2

视频链接 : 

希望下次秒懂的是算法题_哔哩哔哩_bilibili 

P1094 [NOIP2007 普及组] 纪念品分组

原题链接 : 

[NOIP2007 普及组] 纪念品分组 - 洛谷

 思路 :

  1. 排序 + 贪心 + 双指针
  2. 首先先对输入进来的数组进行排序(由小到大)
  3. 运用贪心的思想 : 前后结合,令l=1,r=n,若a[l]+a[r]<=w,那么a[l],a[r]可以成一组，l++,r--,ans++,否则a[r]单独成一组,r--,ans++;(这个求解过程用到双指针的思想);
  4. 该贪心思路在做题的时候想可能是对的，但是没有细究，具体的思想请参考 : 题解 P1094 【纪念品分组】 - heidoudou 的博客 - 洛谷博客

代码 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 3e4+10,mod = 1e9+7;
int n,w,a[N];
LL ans;

inline void solve(){
	cin>>w>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	int l=1,r=n;
	while(l<=r){
		if(a[l]+a[r]<=w){
			l++; r--; ans ++;
		}else {
			r--; ans ++;
		}
	}
	cout<<ans <<endl;
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

 P1102 A-B 数对

原题链接 : 

https://www.luogu.com.cn/problem/P1102

思路 : 

1.直接暴力,当然会tle了,hh( O(n^2) )

2.妙用map;(O(n))

3.用二分函数,upper_bound和lower_bound;对于a[i](a),其后满足 b-a=c的连续区间长度可以用二分函数来求得(当然是对于排好序的数组) O(nlogn)

详细解答请看代码 : 

代码 : 

代码(暴力) : 

 直接暴力,当然会收获tle(3个),hhh 
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;

inline void solve(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if( (LL)(abs(a[i]-a[j])) == c )
				ans ++;
		}
	}
	cout << ans << endl;
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

代码(用map) : 

// map
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;
map<LL,LL> mp;

inline void solve(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
	for(int i=1;i<=n;i++) ans += mp[a[i]-c];
	cout << ans << endl;
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

代码 : (二分) : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10,mod = 1e9+7;
LL n,c,a[N];
LL ans;

inline void solve(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		ans += ((upper_bound(a+1,a+n+1,a[i]+c)-a)-(lower_bound(a+1,a+n+1,a[i]+c)-a));
	}
	cout << ans << endl;
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

P1105 平台

原题链接 : 

平台 - 洛谷

思路 : 

结构体排序 + 暴力,其实不难，要注意细节；

不然，就像这样(aaa) : 

 

第一次排序规则 : 高度优先，编号其次，由小到大；

第二次排序规则 : 编号优先,由小到大;

注意 : 

  1. 边界相同，落到下一个上面，注意结构体排序的规则!!!

代码 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){ return b==0 ? a : gcd(b,a%b); }
LL lcm(LL a,LL b){ return a / gcd(a,b) * b ; }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 1e4+10;
int n,xl,xr;
struct Node{
	int idx,h,l,r,yl,yr;
	bool operator < (const Node &u) const
	{
		return h == u.h ? idx > u.idx : h < u.h;
	}
}a[N];

bool cmp(const Node& x,const Node& y){
	return x.idx < y.idx;
}

inline void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].h>>a[i].l>>a[i].r;
		a[i].idx = i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		xl=0,xr=0;
		for(int j=i-1;j>=1;j--){
			if(a[j].l<a[i].l && a[j].r>a[i].l && a[j].h < a[i].h){
				xl = a[j].idx;
				break;
			}
		}
		for(int j=i-1;j>=1;--j){
			if(a[j].r>a[i].r && a[j].l<a[i].r && a[j].h < a[i].h){
				xr = a[j].idx;
				break;
			}
		}
		a[i].yl = xl;
		a[i].yr = xr;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		cout << a[i].yl << " " << a[i].yr << endl;
	}
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

EK的代码中是用的一个pair<int,int>来存yl,yr信息，思想是一样!!!

P1111 修复公路

原题链接 : 

修复公路 - 洛谷

思路 : 

并查集

代码(cv!):

#include<bits/stdc++.h>
using namespace std;
int fa[1000+10],n,m;
struct node
{
	int x,y,t;
}a[100000+10];//结构体大法好！
bool cmp(node fir,node sec)
{
	return fir.t<sec.t;
}//按照时间排序
int gf(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=gf(fa[x]);
    //这句是路径压缩，前面的题解已经说过，此处不再阐述
}
void hb(int x,int y)
{
	int fx=gf(x);//找到x的祖先
	int fy=gf(y);//找到y的祖先
	fa[fx]=fy;//让fx认fy为祖先
}//合并操作
bool check()
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i) sum++;//统计独立集合的个数
		if(sum==2) return 0;//发现有两个就返回false应该会省一点时间
	}
	return 1;//只有1个集合，返回true
}//判断集合个数
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;//初始化
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
	sort(a+1,a+m+1,cmp);//按时间排序
	for(int i=1;i<=m;i++)
	{
		hb(a[i].x,a[i].y);//进行合并
		if(check())//如果只有1个集合
		{
			printf("%d\n",a[i].t);//输出时间
			return 0;//愉快的结束主程序
		}
	}
	printf("-1\n");//所有公路修完了仍没有联通（集合个数>=2），输出-1
	return 0;//愉快的结束主程序
}

P1115 最大子段和

原题链接 : 

最大子段和 - 洛谷

思路 : 

贪心，由前向后遍历，sum记录和，如果sum<0的话，sum=0(不然的话，只会对后面的sum产生负影响),循环更新ans = max(ans,sum);

代码 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

using namespace std;
typedef long long LL;
int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
int lcm(int a,int b){ if(a==0||b==0) return 0; return (a*b)/gcd(a,b); }
bool is_prime(int x){if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false; return true;}
const int N = 2e5+10;
int n,x;
LL sum=0,ans = -1e9;

inline void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		sum += x;
		ans = max(ans,sum);
		if(sum < 0)	sum = 0;
	}
	cout << ans << endl;
}
 
int main()
{
    IOS
    int _;
    // cin >> _;
    _ = 1; 
    while(_ --) solve();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/95408.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux centos7 bash编程（小练习）

Linux centos7 bash编程（小练习）

一、打印九九乘法口诀 这一个for循环嵌套的小练习&#xff0c;难度不大。提供一种写法&#xff0c;供参考&#xff1a; #!/bin/bash # 文件名&#xff1a;99table.sh # 打印输出九九乘法口诀表 for i in {1..9} do for ((j1;j<$i;j)) do …
阅读更多...
⛳ Docker 安装 MySQL

⛳ Docker 安装 MySQL

&#x1f38d;目录 ⛳ Docker 安装 MySQL&#x1f69c; 一、搜索 mysql , 查看版本&#x1f3a8; 二、拉取mysql镜像&#x1f463; 三、建立容器的挂载文件&#x1f9f0; 四、创建mysql配置文件&#xff0c;my.conf&#x1f3ed; 五、根据镜像产生容器&#x1f381; 六、远程连…
阅读更多...
2023MySQL+MyBatis知识点整理

2023MySQL+MyBatis知识点整理

文章目录 主键 外键 的区别&#xff1f;什么是范式&#xff1f;什么是反范式&#xff1f;什么是事务&#xff1f;MySQL事务隔离级别&#xff1f;MySQL事务默认提交模式&#xff1f;MySQL中int(1)和int(10)的区别MySQL 浮点数会丢失精度吗&#xff1f;MySQL支持哪几种时间类型&a…
阅读更多...
线性数据结构：数组与链表的探索与应用

线性数据结构：数组与链表的探索与应用

文章目录 1. 数组&#xff1a;连续存储的有序元素集合1.1 创建和访问数组1.2 数组的搜索与排序 2. 链表&#xff1a;非连续存储的动态数据结构2.1 单链表与双链表2.2 链表的操作与应用 3. 数组与链表的比较与应用3.1 数组与链表的比较3.2 数组与链表的应用 4. 总结与展望 &…
阅读更多...
【Go 基础篇】切片：Go语言中的灵活数据结构

【Go 基础篇】切片：Go语言中的灵活数据结构

在Go语言中&#xff0c;切片&#xff08;Slice&#xff09;是一种强大且灵活的数据结构&#xff0c;用于管理和操作一系列元素。与数组相比&#xff0c;切片的大小可以动态调整&#xff0c;这使得它成为处理动态数据集合的理想选择。本文将围绕Go语言中切片的引入&#xff0c;介…
阅读更多...
如何在有或没有WiF适配器的情况下把台式机接入WiFi

如何在有或没有WiF适配器的情况下把台式机接入WiFi

Wi-Fi在台式电脑中越来越普遍，但并不是所有的台式电脑都有。添加Wi-Fi，你就可以无线连接到互联网，并为其他设备托管Wi-Fi热点。 这是一个简单、廉价的过程。买一个合适的小适配器，你甚至可以随身携带，通过将一个小设备插入USB端口，可以快速将Wi-Fi添加到你遇到的任何桌面…
阅读更多...
screen命令，可以断开服务器连接，依旧能运行你的程序了

screen命令，可以断开服务器连接，依旧能运行你的程序了

可以参考博客1&#xff1a;https://blog.csdn.net/nima_zhang_b/article/details/82797928 可以参考博客2:https://blog.csdn.net/herocheney/article/details/130984403 Linux中的screen是一个命令行工具&#xff0c;可以让用户在同一个终端会话中创建多个虚拟终端。它非常有…
阅读更多...
element-ui 弹窗里面嵌套弹窗，解决第二个弹窗被遮罩层掩盖无法显示的问题

element-ui 弹窗里面嵌套弹窗，解决第二个弹窗被遮罩层掩盖无法显示的问题

当我们在 element-ui 中使用弹窗嵌套弹窗时&#xff0c;会出现第二个弹窗打开时被一个遮罩层挡着&#xff0c;就像下面这样&#xff1a; 下面提供两种解决方案 &#xff1a; 一、第一种方案 我们查询element-ui 官网可以发现 el-dialog 有这样几个属性&#xff1a; 具体使用就…
阅读更多...
Android Looper Handler 机制浅析

Android Looper Handler 机制浅析

最近想写个播放器demo&#xff0c;里面要用到 Looper Handler&#xff0c;看了很多资料都没能理解透彻&#xff0c;于是决定自己看看相关的源码&#xff0c;并在此记录心得体会&#xff0c;希望能够帮助到有需要的人。 本文会以 猜想 log验证 的方式来学习 Android Looper Ha…
阅读更多...
Jmeter接口测试+压力测试

Jmeter接口测试+压力测试

接口测试 Jmeter-http接口脚本 一般分五个步骤:&#xff08;1&#xff09;添加线程组 &#xff08;2&#xff09;添加http请求 &#xff08;3&#xff09;在http请求中写入接入url、路径、请求方式和参数 &#xff08;4&#xff09;添加查看结果树 &#xff08;5&#xff09;…
阅读更多...
无涯教程-Python机器学习 - Stochastic Gradient Boosting函数

无涯教程-Python机器学习 - Stochastic Gradient Boosting函数

它也称为梯度提升机。在下面的Python食谱中,我们将通过使用pima Indians糖尿病数据集上的 sklearn 的 GradientBoostingClassifier 类来创建随机梯度Boostingensemble模型进行分类。 首先,导入所需的软件包,如下所示: from pandas import read_csv from sklearn.model_select…
阅读更多...
LC1011. 在 D 天内送达包裹的能力(JAVA)

LC1011. 在 D 天内送达包裹的能力(JAVA)

在 D 天内送达包裹的能力 题目描述上期经典算法 题目描述 leetcode 1011. 在 D 天内送达包裹的能力 难度 - 中等 传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天&#xff0c;我们都会按给出重量&#xff08;we…
阅读更多...
oracle 启停操作

oracle 启停操作

1. 监听端口启停 # 根据实际情况 切换至oracle用户 su - oracle# 状态查看 lsnrctl stat# 启动1521端口监听 lsnrctl start# 关闭1521监听 lsnrctl stop 2. 数据库服务启停 # 立即关闭服务 shutdown immediate# 启动服务 startup
阅读更多...
惠普NS1020激光打印机碳粉警告提示及添加碳粉方法

惠普NS1020激光打印机碳粉警告提示及添加碳粉方法

本文也适用于惠普NS1020、1020c 和 1020w 系列打印机。 通过碳粉量指示灯检查碳粉量。 如果碳粉量是满的或指示器显示 1&#xff0c;可选择添加一个碳粉或者忽略不添加。如果碳粉量指示灯显示 2或 2 和碳粉量警告感叹号图标 &#xff0c;则表示碳粉量不足或严重不足&#xff0…
阅读更多...
Stable Diffusion Web UI的原理与使用

Stable Diffusion Web UI的原理与使用

Stable Diffusion是一套基于Diffusion扩散模型生成技术的图片生成方案&#xff0c;随着技术的不断发展以及工业界对这套工程细节的不断优化&#xff0c;使其终于能在个人电脑上运行&#xff0c;本文将从github下载开始讲一讲如何使用Stable Diffusion Web UI进行AI图像的生成。…
阅读更多...
Unity3D Pico VR 手势识别 二

Unity3D Pico VR 手势识别 二

Unity3D Pico VR 手势识别_Cool-浩的博客-CSDN博客 此篇主要讲解怎么手势追踪&#xff0c;手势姿态自定义预制识别&#xff0c;不会导入SDK和配置环境的请看上一章节 环境要求 SDK 版本&#xff1a;2.3.0 及以上PICO 设备型号&#xff1a;PICO Neo3 和 PICO 4 系列PICO 设备系…
阅读更多...
老年人跌倒智能识别算法 opencv

老年人跌倒智能识别算法 opencv

老年人跌倒智能识别算法通过opencvpython深度学习算法框架模型&#xff0c;老年人跌倒智能识别算法能够及时发现老年人跌倒情况&#xff0c;提供快速的援助和救援措施&#xff0c;保障老年人的安全。Python是一种由Guido van Rossum开发的通用编程语言&#xff0c;它很快就变得…
阅读更多...
封装公共el-form表单（记录）

封装公共el-form表单（记录）

1.公共表单组件 //commonForm.vue <script> import {TEXT,SELECT,PASSWORD,TEXTAREA,RADIO,DATE_PICKER } from /conf/uiTypes import { deepClone } from /utils export default {name: GFormCreator,props: {config: { // title/itemstype: Object,required: true}}…
阅读更多...
【人工智能】—_贝叶斯网络、概率图模型、全局语义、因果链、朴素贝叶斯模型、枚举推理、变量消元

【人工智能】—_贝叶斯网络、概率图模型、全局语义、因果链、朴素贝叶斯模型、枚举推理、变量消元

文章目录 频率学派 vs. 贝叶斯学派贝叶斯学派Probability&#xff08;概率&#xff09;:独立性/条件独立性&#xff1a;Probability Theory&#xff08;概率论&#xff09;:Graphical models &#xff08;概率图模型&#xff09;什么是图模型&#xff08;Graphical Models&…
阅读更多...
L1-044 稳赢(Python实现) 测试点全过

L1-044 稳赢(Python实现) 测试点全过

题目 大家应该都会玩“锤子剪刀布”的游戏&#xff1a;两人同时给出手势&#xff0c;胜负规则如图所示&#xff1a; 现要求你编写一个稳赢不输的程序&#xff0c;根据对方的出招&#xff0c;给出对应的赢招。但是&#xff01;为了不让对方输得太惨&#xff0c;你需要每隔K次就…
阅读更多...
最新文章

Copyright @ 2022~2023