【算法训练营】排序,分组,大转盘(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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)

《使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)》PPT是一种高效的信息展示工具,广泛应用于教育、商务和设计等多个领域,PPT文档中常常包含丰富的图片内容,这些图片不仅提升了... 目录一、引言二、环境与工具三、python 提取PPT背景图片3.1 提取幻灯片背景图片3.2 提取

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

一文带你搞懂Python中__init__.py到底是什么

《一文带你搞懂Python中__init__.py到底是什么》朋友们,今天我们来聊聊Python里一个低调却至关重要的文件——__init__.py,有些人可能听说过它是“包的标志”,也有人觉得它“没... 目录先搞懂 python 模块(module)Python 包(package)是啥?那么 __in

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络