day2

Uncategorized
758 words

day2 - 登堂入室

温故而知新

  1. 分治的作用
  2. 分治的思想
  3. 分治的写法(二分查找)

练习题：洛谷 P2249 查找

思考题：洛谷 P1676 Aggressive cows G

排序

桶排序 - 最快的排序

  1. 思想
  2. 优点，适用范围

选择排序 - 打擂台

  1. 思想
  2. 改进
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include<cstdio>
    #include<iostream>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	int a[1001];
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    		
    	//核心代码
    	for(int i=1;i<=n-1;i++){
    		int max=-99999999;
    		int pos;
    		for(int j=i;j<=n;j++){
    			if(a[j]>max){
    				max=a[j];
    				pos=j;
    			}
    		}
    		
    		//交换 
    		int t=a[i];
    		a[i]=a[pos];
    		a[pos]=t;
    		
    	}
    	for(int i=1;i<=n;i++)
    		cout<<a[i]<<" "; 
    	return 0;
    }

插入排序 - 扑克摸牌

  1. 思想
  2. 优点，使用性
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #define len 5
    using namespace std;
    int main()
    {
    	int a[] = {45,32,56,71,12};
    	int i;
    	cout<<"原数组："<<endl; 
    	for(i=0;i<len;i++)
    	{
    		cout<<a[i]<<" ";
    	}
    	printf("\n经过直接插入排序后：\n"); 
    	
    	int j,temp;
    	for(i=1;i<len;i++)
    	{
    		temp = a[i];
    		//当前数小于前一位数时
    		if(a[i] < a[i-1])
    		{
    			//将子序列重新排列为有序序列
    			for(j=i-1;temp<a[j];j--)
    			{
    				a[j+1] = a[j];
    			}
    			a[j+1] = temp;
    		}
    	}
    	
    	for(i=0;i<len;i++)
    	{
    		cout<<a[i]<<" ";
    	}
    }

冒泡排序 - 邻居好说话

  1. 思想
  2. 改进(优化，双向冒泡)
  3. 优点

快速排序 - 用的最多的排序

  1. 思想
  2. 优缺点

更多排序算法 - 进阶

  1. 基数排序
  2. 希尔排序
  3. 归并排序
  4. 堆排序

习题

洛谷

P1177 【模板】排序

P1059 [NOIP2006 普及组] 明明的随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	// 数字是1~1000 
	int b[1001] = {0}; //桶的含义 
	
	int n;
	cin>>n; //n个数据 
	
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		b[x] = 1;//桶排关键代码 
	}
	int total=0; 
	//输出 
	for(int i=1;i<=1000;i++){//有1000个桶 	
		if(b[i]==1){
			total++;
		}		 
	}
	cout<<total<<endl;
	for(int i=1;i<=1000;i++){//有1000个桶 
		if(b[i]==1){
			printf("%d ",i);
		}
			 
	}
	return 0;
}

P1012 [NOIP1998 提高组] 拼数

比较判断的条件，字符串的运用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int i,j,n;
    string st[21];
    
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      	cin>>st[i];
      	
    for(i=1;i<=n-1;i++)
      	for(j=i+1;j<=n;j++)
        	if(st[j]+st[i]>st[i]+st[j])//核心代码 
          		swap(st[j],st[i]);
          		
    for(i=1;i<=n;i++)
      	cout<<st[i];      
                                      
    return 0;  
}

P1051 [NOIP2005 提高组] 谁拿了最多奖学金

P1093 [NOIP2007 普及组] 奖学金

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	int n,score[310],id[310],x[310];//x[]是语文成绩 
	cin >> n;
	for(int i = 1;i <= n; i++){
		int y, z;
		cin>> x[i] >> y >> z ;
		score[i] = x[i] + y + z; 
		
		id[i] = i;
	}    
    for(int i = 1; i <= n - 1; i++)
		for(int j = i + 1; j <= n; j++)
			if(score[i] < score[j] || // 核心判断语句 
				(score[i] == score[j] && x[i] < x[j]) ||
				(score[i] == score[j] && x[i] == x[j] && id[i] > id[j])){
					
				int temp = score[i];
				score[i] = score[j];
				score[j] = temp;     //交换总分 
				
				temp = id[i];
				id[i] = id[j];
				id[j] = temp;		//交换学号 
				
				temp = x[i];
				x[i] = x[j];
				x[j] = temp;		//交换语文成绩 
			}          
	for(int i = 1; i <= 5; i++)      //前5名 
		cout<<id[i]<<" "<<score[i]<<endl;                       
    return 0;  
}