练习1：计数排序 P1271 【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 $n$（$1\le n\le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（$1\le m\le 2000000$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。设第 $i$（$1\le i\le m$）张选票上的数字为 $a_i$，则保证有 $1\le a_i\le n$。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

输入输出样例 #1

输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

输出 #1

1 2 2 2 2 2 2 2 5 5

解题思路

让投票的过程 自行完成排序
如果用数组接收选票再排序，效率非常低下，所以本题需要采用计数排序

参考代码

#include <iostream>
using namespace std;
int main()
{
    int n,m,tmp;
    int e[1010] = {0};
    cin >> n >> m;
    //假设每名候选人身后都有一个投票桶（数组中的一个元素）
    for(int i = 1;i <= m;i++)
    {
        cin >> tmp;    //输入候选人标号
        e[tmp]++;    //对应投票桶的选票数量增加
    }
    
    for(int i = 1;i <= n;i++)   //注意候选人的编号从1开始
    {
        for(int j = 1;j <= e[i];j++)
        {
            cout << i << ' ';
        }
    }
    return 0;
}

选择排序模板

for (int i = 0; i < n-1; i++)
{
	for (int j = i + 1; j < n; j++)
	{
		//将最大值放到指定位置     若是最小则将>改为<
		if (a[j] > a[i])
		{
			int p = a[i];
			a[i] = a[j];
			a[j] = p;   //两个数交换位置 需要p作为中转，不然a[i]就丢失了
		}
	}
}

冒泡排序模板

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n - i - 1; j++)  //每经过一轮排序  最后的第n-i张牌就是max/min 无需再比较
	{
		if (a[j] < a[j + 1]) //由大到小  由小到大则反号
		{
			int p = a[j];
			a[j] = a[j + 1];
			a[j + 1] = p;
		}
	}
}

插入排序模板

背景： 从牌堆里抽牌，如何确保手牌都是有序的呢？

//a[0] -- a[i-1]  已排序区（从左到右 牌从小到大）   a[i] -- a[n-1]  未排序区
for (int i = 1; i < n; i++) //待插入的牌
{
	int now = a[i];  //当前要插入的元素

	int j = i - 1;  //从已排序区的末尾开始比较  比较的起点
	//如果 j牌大 now往前 j往后
	while (j >= 0 && a[j] > now)
	{
		a[j + 1] = a[j];
		j--;
	}
	//如果now大 那么第j+1就是now
	a[j + 1] = now;
}

快速排序# P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开。

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 $20\%$ 的数据，有 $1\le N\le 10^3$；

对于 $100\%$ 的数据，有 $1\le N\le 10^5$，$1\le a_i\le 10^9$。

解题思路

采用分治法和递归法
找到flag 将数组分为两部分
假定左半部分都 < flag 右半部分都 > flag
此时就要从左半部分找到 >flag的数 再在右半部分找到<flag的数
两数对换 不断重复（分治）
然后再递归 对左半部分和右半部分重复上述步骤 （递归）
即可完成排序

参考代码

#include <iostream>
using namespace std;
int a[100005] = {0};
void qsort(int l,int r)
{
    int i = l , j = r , flag = a[(l+r)/2] , tmp;
    
    do
    {
        while(a[i] < flag)
            i++;
        while(a[j] > flag)
            j--;
        if(i <= j)
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }while(i <= j);
    //递归 排序左半部分
    if(l < j)
        qsort(l,j);
    //递归 排序右半部分
    if(i < r)
        qsort(i,r);   
    //所谓递归  就是大事化小 小事化了
}
int main()
{
    int n = 0;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    qsort(1,n);
    for(int i = 1;i <= n;i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

快速排序# P1923 【深基9.例4】求第 k 小的数

题目描述

输入 $n$ 个数字 $a_i$，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

第一行有两个整数，分别表示 $n$ 和 $k$。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

一个整数，表示第 $k$ 小的数。

输入输出样例 #1

输入 #1

5 1
4 3 2 1 5

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$1\le a_i<{10}^9$，$1\le n<5\times 10^6$，且 $n$ 为奇数。

解题思路

主要问题在于如何提速

①使用vector动态数组 优于使用普通数组
②使用随机数随机选取flag（避免每次测试都从中间数选取，可能出现极端情况）
③使用scanf和printf 而不是cin cout

参考代码

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;
int n ,k;
int findkth(vector<int>& a,int l, int r)
{
    //区间内只有一个元素
    if(l == r)
        return a[l];

    int rand_idx = l + rand() % (r-l+1);
    
    int i = l,j = r,flag = a[rand_idx],tmp;
    
    do{
        while(a[i] < flag) i++;
        while(a[j] > flag) j--;
        if(i <= j)
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }while(i <= j);
    //do-while部分结束后 i > j!!!  此时左区（l，j）右区（i，r）

    //递归部分  只取一半分析
    
    //k在右半部分
    if(k >= i)
        return findkth(a,i,r);
    //k在左半部分
    else if(k <= j)
        return findkth(a,l,j);
    //k既不在左，也不在右
    else
        return a[j+1];
}

int main()
{
    srand(time(0));
    scanf("%d %d",&n,&k);
    vector<int> a(n);
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&a[i]);
    }
    int ans = findkth(a,0,n-1);
    printf("%d",ans);
    return 0;
}

计数排序# P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\le 100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例 #1

输入 #1

10
20 40 32 67 40 20 89 300 400 15

输出 #1

8
15 20 32 40 67 89 300 400

说明/提示

NOIP 2006 普及组 第一题

解题思路

（法一）计数排序题型特点：
①固定范围 ②重复数字

模拟投票箱的操作即可，看对应数字重复了多少了
[idx] = 被投票者 票数对应++

去重：
遍历投票箱数组 票数>=1 提取至另一个数组

排序…冒泡 选择 快速 都可
（法一）参考代码

#include <iostream>
using namespace std;
void sort(int arr[],int cnt)
{
    for(int i = 0;i < cnt;i++)
    {
        for(int j = 0;j < cnt - i -1;j++)
        {
            if(arr[j+1] < arr[j])
            {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
int main()
{
    int n,a[1010] = {0},tmp;
    int b[1010] = {0};
    cin >> n;
    //输入   计数排序
    for(int i = 1;i <= n;i++)
    {
        cin >> tmp;
        a[tmp]++;
    }
    int cnt = 0;
    for(int i = 0;i < 1010;i++)
    {
        if(a[i] >= 1)
        {
            b[cnt] = i;
            cnt++;
        }
    }
    sort(b,cnt);
    cout << cnt << endl;
    for(int i = 0;i < cnt;i++)
    {
        printf("%d ",b[i]);
    }
    return 0;
}

（法二）unique 去重 和 sort排序

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int &a,int &b)
{
    return a < b;
}
int main()
{
    int a[1010],n,cnt = 0;
    cin >> n;

    //读取数据
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }

    //按从小到大排序（未去重）   默认升序  cmp不写也可以的
    sort(a,a+n,cmp);

    //去重
    cnt = unique(a,a+n) - a;
    cout << cnt << endl;

    //输出
    for(int i = 0;i < cnt;i++)
        cout << a[i] << ' ';
    return 0;
}

结构体排序

P1093 [NOIP 2007 普及组] 奖学金

题目背景

NOIP2007 普及组 T1

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

7 279  
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、$5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

5 279  
7 279

则按输出错误处理，不能得分。

输入格式

共 $n+1$ 行。

第 $1$ 行为一个正整数 $5\le n\le 300$，表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1\sim n$（恰好是输入数据的行号减 $1$）。

保证所给的数据都是正确的，不必检验。

输出格式

共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

输入输出样例 #1

输入 #1

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出 #1

6 265
4 264
3 258
2 244
1 237

输入输出样例 #2

输入 #2

8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出 #2

8 265
2 264
6 264
1 258
5 258

解题思路

老生常谈 不讲不讲~
注意sort排序的基底即可

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
struct student
{
    int id;
    int c,m,e;
    int t;
}a[310];
bool cmp(student &a,student &b)
{
    if(a.t != b.t)
        return a.t > b.t;
    else if(a.c != b.c)
        return a.c > b.c;
    else
        return a.id < b.id;
}
int main()
{
    int n;
    cin >> n;
    //输入学生数据
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].c >> a[i].m >> a[i].e;
        a[i].t = a[i].c + a[i].m + a[i].e;
        a[i].id = i;
    }
    //排序
    sort(a+1,a+n+1,cmp);    //注意基底是从1开始 所以排序范围要‘整体’向后移1
    //输出
    for(int i = 1;i <= 5;i++)
    {
        cout << a[i].id << ' ' << a[i].t << endl;
    }
    return 0;
}

字典序排序（大数拆分） # P1781 宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的票数。

输入输出样例 #1

输入 #1

5
98765
12365
87954
1022356
985678

输出 #1

4
1022356

说明/提示

$1\le n\le 20$。

票数可能会很大，可能会到 $100$ 位数字。数据保证不存在票数相同的候选人。

解题思路

因为票数可能会很大， 普通数组无法存储，若将该数每一位都拆分， 再统计位数， 再每一位比较，效率非常低下。
所以采用字典存储大数 利用字典序的比较

参考代码

#include <iostream>
#include <string>
using namespace std;
struct node
{
    string x;
    int id;
}a[30];
bool cmp(node &a,node &b)
{
    if(a.x.length() != b.x.length())
        return a.x.length() > b.x.length();
    else 
        return a.x > b.x; //位数相同  比较字典序！！！
}
int main()
{
    int n = 0;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].x;
        a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);
    cout << a[1].id << endl << a[1].x;
    return 0;
}