插入排序
Time Limit: 1000MSMemoryLimit: 65536KB
ProblemDescription
现有 n 个从小到大排列的数组成的序列。需要对这个序列进行 c 次操作。
每次操作有两种类型:
- 操作 1:插入一个数 v 到序列中,并保持有序。
- 操作 2:输出当前的序列。
bLue 并不太擅长序列操作,所以他想来请求你的帮助,你能帮助他完成这个任务吗?
Input
输入数据有多组(数据组数不超过 30),到 EOF 结束。
对于每组数据:
- 第 1 行输入一个整数 n (1 <= n <= 10^5),表示初始的有序序列中数字的个数。
- 第 2 行输入 n 个用空格隔开的整数 ai (0 <= ai <= 10^6),表示初始序列。
- 第 3 行输入一个整数 c (1 <= c <= 1000),表示有 c 次操作。
- 接下来有 c 行,每行表示一次操作:
- 如果操作类型为 1,则输入格式为 "1 v",其中 v (0 <= v <= 1000) 表示要插入到序列的数。
- 如果操作类型为 2,则输入格式为 "2"。
Output
对于每组数据中的每次类型为 2 的操作,输出一行,表示当前的序列,每个数之间用空格隔开。
ExampleInput
5
1 2 2 3 5
5
1 0
2
1 3
1 7
2
ExampleOutput
0 1 2 2 3 5
0 1 2 2 3 3 5 7
Hint
Author
「2016年第六届ACM趣味编程循环赛 Round #2」bLue
I
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
struct node
{
int data;
struct node *prior,*next;
};
struct node*insert(struct node*head,int n)//建立数目为n的双向链表;
{
int i;
struct node*tail,*p;
head = (struct node*)malloc(sizeof(struct node));
head->next =NULL;
head->prior =NULL;
tail = head;
for(i=0;i<n;i++)
{
p = (struct node*)malloc(sizeof(struct node));
scanf("%d",&p->data);
p->next = NULL;
p->prior = tail;
tail->next =p;
tail = p;
}
return head;
}
void find(struct node*head,int m,int n)
{
struct node*p ;
while(m--)
{
int key ,count = 0;
scanf("%d",&key);
p = head->next;
while(p)
{
count++;
if(key==p->data)
{
if(count==1)
{ printf("%d\n",p->next->data);
}
else if(count==n)
{
printf("%d\n",p->prior->data);
}
else
{
printf("%d %d\n",p->prior->data,p->next->data);
}
}
p =p->next;
}
}
}
int main()
{
struct node *head;
head = (struct node*)malloc(sizeof(struct node));
int m,n;
scanf("%d%d",&n,&m);
head = insert(head,n);
find(head,m,n);
return 0;
}
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 104KB
Submit time: 2017-01-13 08:18:18
****************************************************/