第一题：给立方体排序的小明

1.题目

2.问题分析与算法设计思路

由可以交换两个相邻的立方体，很容易想到冒泡排序的算法。我们只需要在冒泡排序的过程中记录需要交换的次数即可。

3.算法实现

有一些注释起来的代码，是我之前用于debug的，忽略即可

#include<iostream>
using namespace std;

int SortMP(int a[], int len_a){
	int count=0; //需要进行交换的次数
	int end=len_a - 2; //遍历尾 
	for(int i=0; i < len_a - 1; i++){
		for(int j=0; j <= end; j++){
			if(a[j] > a[j+1]) {
				int t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
				count++;
			}
		}
		end--;
	}
	return count;
}

int main(){
	int a[10000]={};
	int m=0; //测试用例数 
	int n=0; //立方体数 

	//开始
	cin >> m;
	for(int i = 0; i < m; i++) {
		int count=0; //交换次数 
		int n=0; //立方体数 
		cin >> n;
		
		int count_max=0; //能够接受的最大交换次数 
		count_max = n * (n - 1) / 2 - 1; 
		
		//输入立方体
		for(int j = 0; j < n; j++){
			cin>>a[j];
		}
		
		//测试输入
//		cout<<"input"<<endl;
//		for(int j = 0; j < n; j++){
//			cout<<a[j]<<' ';
//		} 
//		cout<<endl;
		
		//排序 
		count = SortMP(a, n);
//		cout<<"count "<<count<<endl;
		
		//测试“排序成功”
//		cout<<"after sort"<<endl;
//		for(int j = 0; j < n; j++){
//			cout<<a[j]<<' ';
//		}  
//		cout<<endl;
		
		//将立方体置空
		for(int j = 0; j < n; j++){
			a[j] = 0;
		} 
		
		//测试交换次数
//		cout<<"count "<<count<<endl;
//		cout<<"count_max "<<count_max<<endl;
		 
		//判断交换次数 
		if(count <= count_max){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	} 
	return 0;
}

4.运行结果

我这里是每读取一组测试数据，就输出一个结果。这和读完所有数据后在开始输出结果的效果其实是一样的。

5.算法分析

算法的时间复杂度即为冒泡排序的时间复杂度：

(

)

o(n^2)

$o (n^{2})$ 。题中

∗

n<=5*10^4

$n <= 5 * 1 0^{4}$ ，该时间复杂度应该还是可以接受的。

第二题：同时整除的数

1.题目

2.问题分析与算法设计思路

可以每一个种输出结果都使用一个if语句进行判断，这样思路会很简单而清晰。
但显然，对于3、5、7的输出与否，都是可以单独判断的，因此我这里尝试的是将几种情况的输出联系起来。

3.算法实现

#include<iostream>
using namespace std;

int main(){
	int num=0;//输入的整数
	bool by3=0;//能否被3整除 
	bool by5=0;
	bool by7=0; 
	int flag=0;//是否已经被更小的数字整除（用来控制空格的输出）
	
	cin>>num;
	
	if(num % 3 == 0) by3 = 1;
	if(num % 5 == 0) by5 = 1;
	if(num % 7 == 0) by7 = 1;
	
	if(by3) {
		cout<<"3";
		flag=1;
	}
	if(by5) {
		if(flag) cout<<" ";
		cout<<"5";
		flag=1;
	}
	if(by7)	{
		if(flag) cout<<" ";
		cout<<"7";
	}
	
	if(!by3 && !by5 && !by7) cout<<"n";
	
	return 0;
}