【牛客刷题】带你在牛客刷题第五弹（简单排序）

目录

[NOIP2007]纪念品分组

题目描述

思路

AC

[NOIP2007]统计数字 

题目描述

思路

AC

[NOIP2004]火星人 

题目描述

思路

AC

哈喽，今天是我们牛客刷题训练第五弹，今天我们来刷一些简单排序的问题，这些问题相对于之前的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--;  // 右边的指针(下标)减 1cnt++;  // 计数器加 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位数和它们代表的数字：

三进制数

 123132213231312321

代表的数字

 123456

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入描述:

第一行有一个正整数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;
}

运行结果：