【算法训练营】排序,分组,大转盘(python实现)

2024-02-15 14:52

本文主要是介绍【算法训练营】排序,分组,大转盘(python实现),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

排序


描述

给出n个整数,将它们从小到大排序后输出。

输入

第一行为一个正整数n,第二行为n个整数。

输出

输出一行n个整数,表示排序后的n个整数。

样例1输入

5
5 4 2 3 -1

样例1输出

-1 2 3 4 5

限制

对于前30%的数据,n ≤ 100,给出的n个整数的绝对值不超过10;

对于前60%的数据,n ≤ 5000,给出的n个整数的绝对值不超过10^9;

对于另20%的数据,n ≤ 500000,给出的n个整数的绝对值不超过10^5;

对于100%的数据,n ≤ 500000,给出的n个整数的绝对值不超过10^9。

时间:2 sec

空间:256 MB

代码实现


# 读取输入
n = int(input())
arr = list(map(int, input().split()))# 使用Python内置的排序函数进行排序
arr_sorted = sorted(arr)# 输出结果
print(" ".join(map(str, arr_sorted)))

分组


描述

有n个正整数排成一排,你要将这些数分成m份(同一份中的数字都是连续的,不能隔开),同时数字之和最大的那一份的数字之和尽量小。

输入

输入的第一行包含两个正整数n,m。

接下来一行包含n个正整数。

输出

输出一个数,表示最优方案中,数字之和最大的那一份的数字之和。

样例1输入

5 2
2 1 2 2 3

样例1输出

5

样例1解释

若分成2和1、2、2、3,则最大的那一份是1+2+2+3=8;

若分成2、1和2、2、3,则最大的那一份是2+2+3=7;

若分成2、1、2和2、3,则最大的那一份是2+1+2或者是2+3,都是5;

若分成2、1、2、2和3,则最大的那一份是2+1+2+2=7。

所以最优方案是第三种,答案为5。

限制

对于50%的数据,n ≤ 100,给出的n个正整数不超过10;

对于100%的数据,m ≤ n ≤ 300000,给出的n个正整数不超过1000000。

时间:4 sec

空间:512 MB

提示

[大家记得看到“最大的最小”这一类语言,一定要想二分能不能做。]

[我们二分最大的那一份的和d,然后从左向右分组,在一组中,在和不超过d的情况下尽量往右分。若最终分出来的组数小于等于m,则这显然是合法的(我们在分出来的组里随便找个地方切开,总能变到m组,且每组的和不超过d)]

[这个d显然是单调的,即,若和不超过d能分成m组,则和不超过d+1也是能分成m组的,故二分正确。]

代码实现

def check(nums, m, mid):# 判断当前mid是否合法count = 1cur_sum = 0for num in nums:if cur_sum + num > mid:count += 1cur_sum = numelse:cur_sum += numreturn count <= mdef binary_search(nums, m):left, right = max(nums), sum(nums)result = 0while left <= right:mid = (left + right) // 2if check(nums, m, mid):result = midright = mid - 1else:left = mid + 1return result# 读取输入
n, m = map(int, input().split())
nums = list(map(int, input().split()))# 调用二分搜索函数
result = binary_search(nums, m)# 输出结果
print(result)

大转盘


时间限制:1 sec

空间限制:256 MB

问题描述

有一个大转盘,被平分成了 2^n 份。

邓老师还有一个长度为 2^n 的数组 a(下标从 0 开始),其中的每个元素都是 0 或 1。于是邓老师就可以选择大转盘上的一个位置,将 a[0] 填入其中,然后按顺时针顺序依次将 a[1],a[2],…,a[2^n-1] 填入。

对于大转盘上的一个指定位置,邓老师可以从它开始,取出顺时针方向的 n 个位置,并将它们按原顺序拼接起来,得到一个长度为 n 的 01 串,也就是一个 n 位二进制数。我们把这个二进制数称作从这个位置开始的幸运数

显然地,大转盘上共有 2^n 个位置可以获得幸运数,而巧合的是 n 位二进制数恰好也有 2^n 个,所以邓老师希望这些所有的幸运数包含了所有的 n 位二进制数。

请输出一个数组 a,使其满足邓老师的要求。(如果有多解,输出任一即可)

下面是一个 n=3 的例子(即样例)。

输入格式

一行一个整数 n。

输出格式

输出一行 2^n 个字符,第 i 个字符(1<=i<=2^n)表示 a[i-1]。

样例输入

3

样例输出

01011100

数据范围

本题包含 16 个测试点。对于第 i 个测试点(1<=i<=16),满足 n=i。

提示

[如果把所有 n-1 位二进制数建立节点,将所有的 n 位二进制数视为单向边。对于边 x,设其前 n-1 位为 u,后 n-1 位为 v,则其连接 u,v。]

[在这张图上求出欧拉回路,想一想,答案与欧拉回路有何关联呢?]

代码实现

#include <iostream>
#include <vector>
using namespace std;// ================= 代码实现开始 =================
// allOne:全1的二进制数,用于二进制“与运算”,allOne = 2^(n-1) - 1
//vis: vis[i][u]表示从u出发,值为i的边
//ans:答案int allOne;
vector<bool> vis[2];
string ans;//计算2^x
//x:指数
//返回值:2^xint twoPow(int x){return 1 << x;
}//求欧拉回路
//u:当前所有节点void dfs(int u){for (int i = 0; i < 2; ++i){if (!vis[i][u]){int v = ((u << 1) | i) & allOne; //将u左移一位,然后将最低位置为i,再将最高位去掉vis[i][u] = 1;dfs(v);ans.push_back('0' + i); //提示:递归v、加入数字到ans中}}
}
/* 请在这里定义你需要的全局变量 */// 本函数求解大转盘上的数,你需要把大转盘上的数按顺时针顺序返回
// n:对应转盘大小,意义与题目描述一致,具体见题目描述。
// 返回值:将大转盘上的数按顺时针顺序放到一个string中并返回
string getAnswer(int n) {//初始化allOne = twoPow(n - 1) - 1;ans = "";for (int i = 0; i < 2; ++i){vis[i].resize(twoPow(n - 1), 0);}dfs(0);return ans;
}// ================= 代码实现结束 =================int main() {int n;scanf("%d", &n);cout << getAnswer(n) << endl;return 0;
}

这篇关于【算法训练营】排序,分组,大转盘(python实现)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/711705

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、