首页 > 其他分享 >1075 链表元素分类——PAT乙级

1075 链表元素分类——PAT乙级

时间:2024-08-23 19:51:03浏览次数:11  
标签:10 结点 元素 PAT int 1075 链表 start

给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为 18→7→-4→0→5→-6→10→11→-2,K 为 10,则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式:

每个输入包含一个测试用例。每个测试用例第 1 行给出:第 1 个结点的地址;结点总个数,即正整数N (≤105);以及正整数K (≤103)。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。

接下来有 N 行,每行格式为:

Address Data Next

其中 Address 是结点地址;Data 是该结点保存的数据,为 [−105,105] 区间内的整数;Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式:

对每个测试用例,按链表从头到尾的顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

输入样例:

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例:

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

 solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn=1e5+5;
int main()
{
	int start,n,k;
	cin>>start>>n>>k;
	int data[maxn],next[maxn];
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		int tmp;cin>>tmp;
		cin>>data[tmp]>>next[tmp];
	}
	vector<pair<int,int> >list;
	while(start!=-1)//将原始链表排序至list
	{
		cnt++;
		list.push_back({start,data[start]});
		start=next[start];
	}
	vector<pair<int,int> >ans;
	for(auto i:list)//插入小于0的
	{
		if(i.second<0)
		{
			ans.push_back({i.first,i.second});
		}
	}
	for(auto i:list)//插入满足题目条件的
	{
		if(i.second>=0 && i.second<=k)
		{
			ans.push_back({i.first,i.second});
		}
	}
	for(auto i:list)//插入剩余的
	{
		if(i.second>k)
		{
			ans.push_back({i.first,i.second});
		}
	}
	for(int i=0;i<ans.size()-1;i++)
	{
		printf("%05d %d %05d\n",ans[i].first,ans[i].second,ans[i+1].first);
	}
	printf("%05d %d -1\n",ans[cnt-1].first,ans[cnt-1].second);
}

标签:10,结点,元素,PAT,int,1075,链表,start
From: https://blog.csdn.net/flyidj/article/details/141469502

相关文章

  • 1110 区块反转——PAT乙级
    给定一个单链表L,我们将每K个结点看成一个区块(链表最后若不足K个结点,也看成一个区块),请编写程序将L中所有区块的链接反转。例如:给定L为1→2→3→4→5→6→7→8,K为3,则输出应该为7→8→4→5→6→1→2→3。输入格式:每个输入包含1个测试用例。每个测试用例第1行给......
  • 读论文《Behavior Pattern Mining-based Multi-Behavior Recommendation》
    论文地址:arxiv.org/pdf/2408.12152v1项目地址:GitHub-rookitkitlee/BPMR基于行为模式挖掘的多行为推荐:论文提出了一种新颖的多行为推荐算法(BPMR),旨在通过分析用户和项目之间的复杂交互模式来提高推荐系统的有效性。这种方法特别关注于用户除了购买之外的其他行为,例如页面浏览......
  • Python - Concurrency and Asynchronous Patterns
    Concurrencyallowsyourprogramtomanagemultipleoperationssimultaneously,leveragingthe fullpowerofmodernprocessors.It’sakintoachefpreparingmultipledishesinparallel,eachstep orchestratedsothatalldishesarereadyatthesametime.......
  • 力扣: 移除链表元素
    文章目录需求虚拟头结点法原头结点法结尾需求给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输......
  • 【408DS算法题】022基础-递增输出单链表中的结点值
    Index题目分析实现总结以上内容稍后补全,以下内容来自https://blog.csdn.net/weixin_60702024/article/details/141336041题目分析实现总结分析题目给定单链表的头结点,按照递增的顺序,输出单链表结点的值。分析实现具体实现如下:总结注意delete执行后,只会将......
  • C++ 链表
    1.前言链表:不仅存储 当前元素的数据,还存储着 元素排列顺序2. 正题2.1如何存储节点?我们可以使用结构体 数组来存储 链表节点structNode{intval;//可以是string或其它复杂的类型intnxt;}node[N];Tip:下标顺序不是单链表顺序 val代表 元......
  • 数据结构--链表(单向链表--有头链表、无头链表)链表的插入、删除、修改、查找
    什么是链表?链表是一种基本的数据结构,用于存储一组数据元素。与数组不同,链表的元素在内存中并不连续存储。链表由一系列节点组成,每个节点包含以下两个主要部分:1.数据部分:存储节点所包含的数据。2.指针部分:存储指向下一个节点的指针(对于单向链表),或者存储指向前一个节点和下......
  • 数据结构之链表(看不懂你来找我)
    数据结构......
  • python 04-标准库:pathlib模块
    pathlib模块pathlib模块‌:是面向对象的文件系统路径操作库,提供接口来处理文件路径。Path是主类Path:Path对象表示文件或目录的路径,Path类会自动选择PosixPath或WindowsPath,具体取决于我们的操作系统......
  • python03-标准库 第三方库-pathlib模块
    python标准库:Python自带的一组模块和库,这些模块和库提供了Python编程所需的基础功能和工具https://docs.python.org/zh-cn/3/library/index.html?eqid=8ca0b3ea000067990000000264800802Python包索引:即PyPI(PythonPackageIndex),是一个仓库,存放了许多可以通过pip安装的独......