哈喽，今天是我们牛客刷题训练第五弹，今天我们来刷一些简单排序的问题，这些问题相对于之前的C/C++基础来说难度肯定是高出了一些，但是我相信，只要我们一步步去分析，最后肯定是可以得到正确的答案的，来我们一起加油。
[NOIP2007]纪念品分组
题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入描述:
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 p_i ( 5 ≤ p_i ≤ w )pi(5≤pi≤w) ，表示所对应纪念品的价格。
输出描述:
包含一个整数，即最少的分组数目。
示例1
输入
100
9
90
20
20
30
50
60
70
80
90
输出
6
备注:
50%的数据满足：1 ≤ n ≤ 151≤n≤15
100%的数据满足：1 ≤ n ≤ 30000, 80 ≤ w ≤ 2001≤n≤30000,80≤w≤200
思路
对于这个题目，我们才用的思路是，先将数组里的价格由小到大进行排序，之后我们定义两个指针，分别指向其左右两边，接下来我们从两边到中间同时操作，如果同时指针指向的元素之和比我们的要求要低的话，我们就将这两个元素放入一组，同时两个指针分别向内移动一位；当然如果两个元素之和大于我们的规定金额的话，那么我们就将价格高的元素单独分至一组，之后其指针内移一位，然后继续进行比较。
这样下来就能使分的组数最少。
我们为什么要这样去进行求呢，我们来思考一下，在两端的元素分别是价格最高的元素和价格最低的元素，如果这两个元素之和没有超过我们所规定的金额时，那对于其他元素来说，都可以与第一个元素所组合，但是最大的元素并不能确定可以跟第一个元素后面的元素进行组合，那我们将这两个元素放在一起，就可以很好的避免一个单独的分组出现，同理倒数第二个，倒数第三个也可以这样思考。
当我们两个价格相加均大于其总金额时，这时我们应该将较大的元素拿出，因为在此时，我们左边元素是没有分组的最小元素，所以当这时都会大于其最大金额时，我们其他的元素与右边元素相加肯定也会大于其规定金额的，那我们就将最大的元素单独分组，然后再进行操作就可以了。
AC
#include<iostream> #include<algorithm> using namespace std; const int N = 3e4 + 10; int a[N]; // 用来存储纪念品的价格 int main() { int w; // 每组纪念品价格之和的上限。 int n; // 纪念品的个数 cin >> w >> n; for (int i = 1; i <= n; i++) { // 输入 n 个纪念品的价格 cin >> a[i]; } sort(a + 1, a + n + 1); // 将纪念品的价格升序排序(按照价格从低到高进行排列) int l = 1; // 左边的指针(其实是表示下标的) int r = n; // 右边的指针(其实是表示下标的) int cnt = 0; // 计数器，用来记录组数 while (l <= r) { // 当左边的指针小于等于右边的指针时，记得要有等号 if (a[l] + a[r] <= w) { // 若两者之和小于等于 w，可以分成一组 l++; // 左边的指针(下标)加 1 r--; // 右边的指针(下标)减 1 cnt++; // 计数器加 1，a[l] 和 a[r] 作为一组，组数加 1 } else { // 若不能分成一组 r--; // 右边的指针(下标)减 1 (左边的指针不变) cnt++; // 计数器加 1，a[r] 自己作为一组 } } cout << cnt; // 输出计数器，即为最少的组数 return 0; }
运行结果：
[NOIP2007]统计数字
题目描述
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
输入描述:
第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
输出描述:
输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
示例1
输入
8
2
4
2
4
5
100
2
100
输出
2 3
4 2
5 1
100 2
备注
40%的数据满足：1 ≤ n ≤ 1000
80%的数据满足：1 ≤ n ≤ 50000
100%的数据满足：1 ≤ n ≤ 200000，每个数均不超过1500000000（1.5*109）
思路
这道题目我在这里使用的是一种非常简单的方法，就是首先我们先将数组里的元素按从小到大进行排序，排序完成后我们设定一个参照数和一个总数（每个元素的）
然后我们从前到后逐个遍历，如果后面元素与前面相同就总数++，否则的话我们输出前面一个元素和总数，之后再将总数设为1（切记这里要设置成1）因为我们当前元素与前面元素不想等，这就是一个新的元素，也就是我们这个元素也就是第一个。
就这样我们循环完成后，对应的输出也就完成了。
AC
#include<iostream> #include<algorithm> using namespace std ; int a[200010] ; //数组存放所有数 int main() { int n ; cin >> n ; for(int i=0; i<n; i++) { cin >> a[i] ; } sort(a, a+n) ; //从小到大进行排序 int sum = 0 ; //相同数字元素个数 int s = a[0] ; //进行比较的元素 for(int i=0; i<n; i++) { if(s == a[i]) sum++ ; //如果后面元素与前面相同 else{ cout << a[i-1] <<" " << sum << endl ; //后面元素与前面不同 s = a[i] ; sum = 1 ; } } cout << a[n-1] << " " << sum << endl ; //输出最后一组数据 return 0 ; }
运行结果：
[NOIP2004]火星人
题目描述
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
输入描述:
第一行有一个正整数N，表示火星人手指的数目（1 <= N <= 10000）（1≤N≤10000）。
第二行是一个正整数M，表示要加上去的小整数（1 <= M<= 100）（1≤M≤100）。
下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。
输出描述:
输出只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。
示例1
输入
5
3
1 2 3 4 5
输出
1 2 4 5 3
思路
这道题目有点难理解，我来给大家解释一下。
1.获取输入n，m
2.获取火星人手指的排列顺序，存放在数组a[N]中
3.加m的结果相当于，以当前排列顺序为基础，进行m次全排列后的排列顺序。因此循环m次，调用next_permutation函数进行全排列
4.输出m次全排列后的数组a，以空格隔开
是不是解释完之后就发现题目变得清晰了很多。
全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
所以我们可以调用C++STL库中的函数，也就是next_permutation ，也就是全排列函数；
其函数原型为：
#include <algorithm> bool next_permutation(iterator start,iterator end)
next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。
大概就是这么个意思， 所以我们只需执行m次全排列就可以了。
AC
#include<cstdio> #include<algorithm> #include<iostream> using namespace std ; const int max_n = 10010; int num[max_n] ; int main() { int n,m ; while( scanf("%d%d",&n,&m) == 2) { for( int i = 0; i < n; i++) scanf("%d",&num[i]); for( int i = 0; i < m; i++) next_permutation(num,num+n); //进行m此全排列 for( int i = 0; i < n; i++) printf(i==n-1?"%d\n":"%d ",num[i]); } return 0; }
运行结果：
