当前位置: 首页 > news >正文

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

目录

[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--;  // 右边的指针(下标)减 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;
}

运行结果:

刷题对程序员来说及其重要,语言和开发平台不断变化,但是万变不离其宗的是那些算法和理论,刷题最最最直白的原因就是找一个好的工作,所以刷题一定是必不可少的

现关于刷题平台还是蛮多的,给大家介绍一个我认为与大厂关联最深的平台——牛客网

9299e0de95fd850d19deef08f3eb6465.png

相关文章:

  • Fragment切换的方式介绍和一些问题的解决
  • 性能优化之图片懒加载
  • Linux多线程篇【5】——线程池
  • 指针成员操作符
  • python中应对各种机制
  • css实现时钟
  • “蔚来杯“2022牛客暑期多校训练营8 补题题解(F)
  • 【数据结构与算法】之深入解析“解出数学表达式的学生分数”的求解思路与算法示例
  • 给妈妈做个相册——在服务器上搭建Lychee相册的保姆级教程
  • 编程之路22
  • 适配器模式是个啥,在Spring中又用来干啥了?
  • 183. 从不订购的客户—not in()、左连接
  • LED灯实验
  • vue中ref的作用
  • JSP简介
  • Angular6错误 Service: No provider for Renderer2
  • Kibana配置logstash,报表一体化
  • linux学习笔记
  • Redux 中间件分析
  • 从PHP迁移至Golang - 基础篇
  • 得到一个数组中任意X个元素的所有组合 即C(n,m)
  • 经典排序算法及其 Java 实现
  • 前端面试之闭包
  • 实现简单的正则表达式引擎
  • 适配mpvue平台的的微信小程序日历组件mpvue-calendar
  • - 语言经验 - 《c++的高性能内存管理库tcmalloc和jemalloc》
  • 运行时添加log4j2的appender
  • 怎么把视频里的音乐提取出来
  • 整理一些计算机基础知识!
  • 组复制官方翻译九、Group Replication Technical Details
  • ​​快速排序(四)——挖坑法,前后指针法与非递归
  • #13 yum、编译安装与sed命令的使用
  • #LLM入门|Prompt#1.7_文本拓展_Expanding
  • #我与Java虚拟机的故事#连载07:我放弃了对JVM的进一步学习
  • (附源码)计算机毕业设计SSM疫情居家隔离服务系统
  • (蓝桥杯每日一题)love
  • (完整代码)R语言中利用SVM-RFE机器学习算法筛选关键因子
  • .NET LINQ 通常分 Syntax Query 和Syntax Method
  • .net mvc actionresult 返回字符串_.NET架构师知识普及
  • .NET 中各种混淆(Obfuscation)的含义、原理、实际效果和不同级别的差异(使用 SmartAssembly)
  • .NET大文件上传知识整理
  • .net开发引用程序集提示没有强名称的解决办法
  • .net快速开发框架源码分享
  • /etc/X11/xorg.conf 文件被误改后进不了图形化界面
  • /proc/stat文件详解(翻译)
  • ?php echo $logosrc[0];?,如何在一行中显示logo和标题?
  • [1]-基于图搜索的路径规划基础
  • [1159]adb判断手机屏幕状态并点亮屏幕
  • [2016.7 test.5] T1
  • [8-27]正则表达式、扩展表达式以及相关实战
  • [Android Pro] listView和GridView的item设置的高度和宽度不起作用
  • [bzoj1006]: [HNOI2008]神奇的国度(最大势算法)
  • [BZOJ1040][P2607][ZJOI2008]骑士[树形DP+基环树]
  • [BZOJ2281][SDOI2011]黑白棋(K-Nim博弈)
  • [C++] sqlite3_get_table 的使用