Peter算法小课堂—自定义容器

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

太戈编程第308题

暴力法

cin>>n>>m;
for(int i=0;i<n;i++) cin>>name[i]>>year[i];
for(int i=0;i<m;i++){
	int x;
	string y;
	cin>>x>>y;
	int OK=0;
	for(int j=0;j<n;j++){
		if(name[j]==y&&year[j]==x){
			OK=1;
			break;
		}
	}
	cout<<OK<<" ";
}

这个算法复杂度为O(nm),显然有更快的算法

自定义类型

Peter算法小课堂—自定义容器,算法,数据结构

 但是,这样写有个很危险的错误,如下

#include <bits/stdc++.h>
using namespace std;
struct dog{
	string name;
	int year;
};
int main(){
	set<dog> s;
	dog a,b;
	a.name="mike";a.year=2020;
	b.name="wangcai";b.year=2019;
	s.insert(a);
	s.insert(b);
	return 0;
}

运行出来是这样的,

Peter算法小课堂—自定义容器,算法,数据结构

 原因很简单,因为set的功能是排序、去重,然而结构体排序要加上“.",所以会报错

改后代码,

#include <bits/stdc++.h>
using namespace std;
struct dog{
	string name;
	int year;
	bool operator<(const dog&d)const {
		if(year<d.year) return 1;
		if(year>d.year) return 0;
		if(name<d.name) return 1;
		return 0;
	}
};
int main(){
	set<dog> s;
	dog a,b;
	a.name="mike";a.year=2020;
	b.name="wangcai";b.year=2019;
	s.insert(a);
	s.insert(b);
	return 0;
}

那么,回到原题,代码该怎么写呢?

#include <bits/stdc++.h>
using namespace std;
struct dog{
	string name;
	int year;
	bool operator<(const dog&d)const {
		if(year<d.year) return 1;
		if(year>d.year) return 0;
		if(name<d.name) return 1;
		return 0;
	}
};
int main(){
	set<dog> s;
	dog d;
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>d.name>>d.year;
		s.insert(d);
	}
	for(int i=0;i<m;i++){
		cin>>d.year>>d.name;
		if(s.count(d)) cout<<"1";
		else cout<<"0";
	}
	return 0;
}

太戈编程第1497题

无set

#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
	int id,score;
	bool operator<(const student&b)const {
		if(score>b.score) return 1;
		if(score<b.score) return 0;
		if(id<b.id) return 1;
		return 0;
	}
};
student f[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>f[i].score;
		f[i].id=i;
	}
	sort(f+1,f+1+n);
	for(int i=1;i<=n;i++){
		cout<<f[i].id<<" "<<f[i].score<<endl;
	}
	return 0;
}

有set

#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
	int id,score;
	bool operator<(const student&b)const {
		if(score>b.score) return 1;
		if(score<b.score) return 0;
		if(id<b.id) return 1;
		return 0;
	}
};
int main(){
	int n;
	cin>>n;
	set<student> s;
	student x;
	for(int i=0;i<n;i++){
		cin>>x.score;
		x.id=i+1;
		s.insert(x);
	}
	set<student>::iterator it;
	for(it=s.begin();it!=s.end();it++)
		cout<<(*it).id<<" "<<(*it).score<<endl;
	return 0;
}

当然这个代码也有高级版,但要升级到c++14,如下

//不推荐使用,OJ好像不行
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
struct student{
	int id,score;
	bool operator<(const student&b)const {
		if(score>b.score) return 1;
		if(score<b.score) return 0;
		if(id<b.id) return 1;
		return 0;
	}
};
int main(){
	int n;
	cin>>n;
	set<student> s;
	int x;
	for(int i=0;i<n;i++){
		cin>>x;
		s.insert({i+1,x});
	}
	set<student>::iterator it;
	for(it=s.begin();it!=s.end();it++)
		cout<<(*it).id<<" "<<(*it).score<<endl;
	return 0;
}

太戈编程第309题

大家认真敲代码15min,15min后开讲

Peter算法小课堂—自定义容器,算法,数据结构

 

#include <bits/stdc++.h>
using namespace std;
struct ren{
	int x,id;
	bool operator<(const ren&b)const{
		if(x<b.x) return 1;
		if(x>b.x) return 0;
		if(id<b.id) return 1;
		return 0;
	}
};
int main(){
	int n;
	cin>>n;
	set<ren> s;
	set<ren>::iterator it;
	ren d;
	for(int i=1;i<=n;i++){
		cin>>d.x;
		d.id=i;
		s.insert(d); 
	}
	set<int> ok;
	for(int i=1;i<=n;i++){
		it=s.begin();
		d.x=(*it).x+3;
		d.id=(*it).id;
		s.erase(it);
		s.insert(d);
		ok.insert(d.id);
	}
	cout<<n-ok.size()<<endl;
	return 0;
}

希望这些对大家有用,三联必回文章来源地址https://www.toymoban.com/news/detail-755882.html

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

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

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

相关文章

  • Peter算法小课堂—线性dp

    今天,你读完这篇文章,普及组的动态规划已经可以秒了。 求两个数列的最长公共子序列(Longest Common Subsequence,LCS)的长度。 数列 X 和 Y 的最长公共子序列 Z,是指 Z 既是 X 的子序列,又是 Y 的子序列,而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。 f[i][j]表示

    2024年04月23日
    浏览(33)
  • Peter算法小课堂—贪心与二分

    题目描述: 有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元,只能买价格不超过其现金额的车子。你是大卖场总经理,希望将车和买家尽量多地进行一对一配对,请问最多卖出多少辆车? 贪心法模板: 比如说:每次挑最便

    2024年02月02日
    浏览(36)
  • Peter算法小课堂—拓扑排序与最小生成树

    讲拓扑排序前,我们要先了解什么是DAG树。所谓DAG树,就是指“有向无环图”。请判断下列图是否是DAG图 第一幅图,它不是DAG图,因为它形成了一个环。第二幅图,它也不是DAG图,因为它没有方向。第三幅图才叫真正的DAG图(DAG图不一定联通)。 那什么叫DAG图的拓扑排序呢

    2024年01月21日
    浏览(46)
  • 【数据结构】二叉树算法讲解(定义+算法原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月23日
    浏览(50)
  • 数据结构期末复习(1)学科定义、组成、算法的定义、时间复杂度比较

    目录 数据结构的几个方面 逻辑结构的描述 逻辑结构 存储结构 数据运算 数据结构和数据类型 数据类型 抽象数据类型(ADT) 算法及其描述 什么是算法 算法分析 算法的设计目标 算法时间性能分析 计算算法频度 算法时间复杂度 简化的算法时间复杂度分析 数据结构学科定义:

    2024年02月03日
    浏览(42)
  • Python课堂12——六大数据结构之集合

    Python中的数据结构马上就要结束了,今天我们来学习Python中六大数据结构的最后一部分集合,坚持就是胜利go! 集合是一种数据类型,用于存储一组唯一的元素。集合可以通过花括号 {} 来定义,元素之间使用逗号分隔。与列表和元组不同,集合中的元素是无序的,且不允许重

    2024年02月22日
    浏览(34)
  • 【算法与数据结构】3 知行合一,线性查找的自定义类测试

    欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享,与更多的人进行学习交流 本文收录于算法与数据结构体系专栏, 本专栏 对于0基础者极为友好,欢迎与我一起完成算法与数据结构的从0到1的跨越 ☑️首篇详细讲述线性查找法并且对其进行了 初步的优化 :👉传送门

    2023年04月27日
    浏览(46)
  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(48)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(54)
  • 数据结构和算法学习记录——平衡二叉树(基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度)

    目录 基本介绍 平衡因子 平衡二叉树  平衡二叉树的高度  什么是平衡二叉树? 以一个例子来解释一下: 搜索树结点按不同的插入次序,将会导致不同的深度和平均查找长度ASL   在二叉搜索树中查找一个元素:  (a)要找到Jan,需要查找一次;要找到Feb,需要查找两次;

    2023年04月26日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包