秒懂算法2

这篇具有很好参考价值的文章主要介绍了秒懂算法2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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

原题链接 : 

 思路 :

代码 : 

 P1102 A-B 数对

原题链接 : 

思路 : 

代码 : 

代码(暴力) : 

代码(用map) : 

代码 : (二分) : 

P1105 平台

原题链接 : 

思路 : 

代码 : 

P1111 修复公路

原题链接 : 

思路 : 

P1115 最大子段和

原题链接 : 

思路 : 

代码 : 


视频链接 : 

秒懂算法2

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) : 

秒懂算法2,洛谷,算法学习,算法,数据结构

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

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

注意 : 

  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);文章来源地址https://www.toymoban.com/news/detail-681465.html

代码 : 

#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;
}

到了这里,关于秒懂算法2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 学习数据结构和算法的第8天

    进行头插 eg:在数组 1 2 3 4 5的开头插入-1 变成-1 1 2 3 4 5 头删 eg:数组1 2 3 4 5 删去1

    2024年02月22日
    浏览(37)
  • 深入学习与探索:高级数据结构与复杂算法

    🎉欢迎来到数据结构学习专栏~深入学习与探索:高级数据结构与复杂算法 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页:IT·陈寒的博客 🎈该系列文章专栏:数据结构学习 📜其他专栏:Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技术和

    2024年02月09日
    浏览(45)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(44)
  • 【一起学习数据结构与算法】优先级队列(堆)

    如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样,我们就引入了 优先级队列 这种数据结构。 优先级队列(priority queue) 是0个或多个元素的集

    2024年01月19日
    浏览(42)
  • 数据结构与算法这么难,为什么我们还要学习?

    提到数据结构与算法,就一定会伴随着诸多所谓的坚持和抱怨。同时,还有两个词总是出现,一个是内功,是对知识的定位,一个是吃透,是对自己

    2024年01月19日
    浏览(57)
  • 数据结构与算法学习(day4)——解决实际问题

    在本章的学习此前,需要复习前三章的内容,每个算法都动手敲一遍解题。宁愿学慢一点,也要对每个算法掌握基本的理解! 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法,今天我们来实践一下前面的三种算法。 本章的学习目标: (1)回顾三个算法的基本原

    2024年02月09日
    浏览(57)
  • 【软考程序员学习笔记】——数据结构与算法基础

    目录  🍊一、数据结构概念和分类 🍊二、数组特点存储方式 🍊三、矩阵 特殊矩阵 非特殊矩阵 🍊四、栈和队列 🍊 五、二叉树的性质 🍊六、二叉树的遍历 (1)前序遍历(先根遍历,先序遍历) (2)中遍历(中根遍历) (3)后序遍历(后根遍历,后序遍历) 🍊七、二叉排序树 🍊八、

    2024年02月12日
    浏览(62)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(78)
  • 学习高级数据结构:探索平衡树与图的高级算法

    🎉欢迎来到数据结构学习专栏~学习高级数据结构:探索平衡树与图的高级算法 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页:IT·陈寒的博客 🎈该系列文章专栏:数据结构学习 📜其他专栏:Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技

    2024年02月09日
    浏览(46)
  • 数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    目录 一、定义和术语 二、存储结构 1、邻接矩阵 1.1、邻接矩阵优点 1.2、邻接矩阵缺点 2、邻接表 3、邻接矩阵和邻接表的区别和用途 3.1、区别 3.2、用途 三、宏定义 四、结构体定义 1、邻接矩阵 2、邻接表 3、网数据类型(造测试数据) 五、函数定义 1、使用邻接矩阵创建无

    2024年02月14日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包