蓝桥杯练习004

1.试题 算法训练 数组移动

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

初始数组A[N]中为1,2,…,N，N个数字，现要进行M次操作，每次操作给定一个数字i，记其在数组中的位置为Bi，将A[1]…A[Bi]移到数组末尾。

输入格式

输入的第一行包含两个整数N,M。接下来M行，每行一个正整数，表示给定的数字i。

输出格式

一行，输出M次操作后的A数组。

样例输入

5 2
3
2

样例输出

3 4 5 1 2

样例说明

第一次操作后变为 4 5 1 2 3

第二次操作后变为 3 4 5 1 2

数据规模和约定

N<=10^5,M<=10 ^ 5

解题思路

1.首先将数组初始化

2.对数组的数据进行移动

3.利用迭代器比较方便

代码实现

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
int main(){
	vector<int> vec;
	int N,M,t;
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		vec.push_back(i);
	}
	vector<int>::iterator it=vec.begin();//定义迭代器it
	for(int i=0;i<M;i++){//输入M组数据 只有最后一个数据是我们需要的
		cin>>t;
	}
	for(int i=0;i<N;i++){//for循环找it位置
		if(*it!=t){
			it++;
		}
	}
	for(int i=0;i<N;i++){
		it++;
		if(it==vec.end()){//实现循环链表的功能 
			it=vec.begin();
		}
		cout<<*it<<" ";
	}
	return 0;
}

2.数组元素循环右移问题

题目要求：

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0A1⋯AN-1）变换为（AN-M⋯AN-1A0A1⋯AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：

每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

输出格式：

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

6 2
1 2 3 4 5 6

输出样例：

5 6 1 2 3 4

解题思路：

循环右移n位可以分解为n个循环右移1位的操作。可以先将数组最右端的数先存起来，再进行右移1位的操作，接着将刚才所存放的数放置在数组首尾（arr[0]），这就是一次循环右移1位的操作。执行n次即可。

代码：

#include <stdio.h>
int main()
{
	int N,arr[1000],n;
	scanf("%d%d",&N,&n);
	for(int i = 0; i < N; i++) {
		scanf("%d",&arr[i]);
	}
	for(int j = 0; j < n; j++) {
		int t =	arr[N-1];
		for(int i = N - 2; i >= 0; i--)
			arr[i + 1] = arr[i];
		arr[0] = t;
	}
	for(int i = 0;i < N;i ++)
		if(i != N - 1)
			printf("%d ", arr[i]);
		else
			printf("%d", arr[i]);
	return 0;
}

另外一种巧妙方式：

思路：存取元素的时候从第m位开始存，将最后的m位从数组开始位置存放

代码：

#include<stdio.h>
int main()
{
	int n,m;
	int a[1000];
	scanf("%d %d",&n,&m);
	m = m % n;//循环
	int cnt = m;//cnt表示右移几位
	while(m<n)
	{
		scanf("%d",&a[m]);//从第m位之后开始存
		m++;
	}
	for(int i=0;i<cnt;i++)
		scanf("%d",&a[i]);//将最后的m位从数组开始位置存放
	int first=1;
	for(int i=0;i<n;i++)
	{
		if(!first)printf(" ");//控制空格的输出
		printf("%d",a[i]);
		first=0;
	}
	return 0;
}

最后

以上就是可耐滑板为你收集整理的蓝桥杯练习004蓝桥杯练习004的全部内容，希望文章能够帮你解决蓝桥杯练习004蓝桥杯练习004所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。