圆桌(满足客人空座需求，合理安排客人入座圆桌，准备最少的椅子)
CSDN周赛第30期第四题算法解析。
-
Python 官网：https://www.python.org/
-
Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……
地址：https://lqpybook.readthedocs.io/
自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
—— 华罗庚
- My CSDN主页、My HOT博、My Python 学习个人备忘录
- 好文力荐、 老齐教室
本文质量分：
CSDN质量分查询入口：http://www.csdn.net/qc
- ◆圆桌
- 1、题目描述
- 2 、应考代码
- 3、解题算法解析
- 3.1 算法分析
- 3.2 左右空座相同
- 3.3 左右空座不等
- 3 优化代码
- 2、
- 2.1
- 3、
- 3.1
- 4、完整源码
◆圆桌
1、题目描述
【CSDN周赛第30期第四题】
题目 4/4 (25 分)
题目名称：圆桌
时间限制：1000ms内存限制：256M
有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边，但是每位客人希望自己左右边上分别有一些空座位，不然会觉得害羞。注意，如果一个客人所在的圆桌只有他一个人，那么他左边的空座位数量就是他右边的空座位数量。 试问主人需要准备多少个座位，才能让每个客人舒适的坐下。
输入描述：
第一行输入一个整数N，(1<=N<=10000),代表客人的数量 接下来N行，每行两个整数li与ri，(1<=i<=N,1<=li<=ri<=1000000000) 代表第i位客人希望左边有li个空座位，右边有ri个空座位。
输出描述：
输出一个整数，代表主人需要准备的最少座位数量。
示例1
输入
3
1 1
1 1
1 1
输出
6
示例2
输入
4
1 2
2 1
3 5
5 3
输出
15
提示
【样例解释】3个人围成一桌，每人左右各一个空位置，一共3个空座位。一个共需要3+3=6座位。
2 、应考代码
应考答题截屏图
应试时，我连题目都没有理清，所以写出了“不知所云”的代码。
3、解题算法解析
3.1 算法分析
3.2 左右空座相同
3.3 左右空座不等
“注意，如果一个客人所在的圆桌只有他一个人，那么他左边的空座位数量就是他右边的空座位数量。”题目描述中的这句话就是说，任何空座需求的客人，都可以可以单独坐一桌的，因为其左右空座会连在一起，不会违背“他左边的空座位数量就是他右边的空座位数量”。但如不拼桌则会算多空座，如示例2，分4桌坐，就应该是3 3 6 6，共需18把椅子。
3 优化代码
2、
2.1
3、
3.1
4、完整源码
#!/sur/bin/nve python
# coding: utf-8'''CSDN周赛第30期第04题：圆桌'''def table(n, lis):''' 计算桌数和需准备座位数 '''result = 0 # 需求空座位数初值。temp = [] # 相同空座需求客人统计列表初始化。while lis: # 统计同桌客人。tem = [lis[0]]l, r = lis[0]lis.pop(0)for i in lis[:]: # 这里一定要遍历用切片复制lis[:]，因为lis可能“动态”变短。li, ri = iif li == r: tem.append(i)lis.remove(i)r = riwhile len(tem) > 1:l0, ri = tem[-1][1], tem[0][0]if ri == l0:break # 客人空座链能首尾相接围坐一桌，退出检验循环。else: # 否则，把最后一位客人退回客人空座信息列表lis。lis.append(tem.pop())temp.append(tem)print(f"\n{'':~^50}\n客人分桌信息数组：\n{temp}\n{'':~^50}")for i in temp:if len(i) == 1:result += sum(i[0])continueresult += sum(j[0] for j in i)return len(temp), result + n # 返回客人桌数和需准备的椅子总数(空座数+客人数)。if __name__ == '__main__':n = int(input('\n输入：\n'))lis = [tuple(map(int, input().strip().split())) for i in range(n)]t = table(n, lis)print(f"\n输出：\n{t[1]}\n\n客人需坐{t[0]}桌，共要准备{t[1]}个椅子。")__上一篇：__ re.findall获取CSDN博文阅读点赞收藏和评论实时数据(学用curl命令获取博文页面源码，学不会爬虫先手剥CSDN博文阅读点赞收藏和评论实时数据。)
__下一篇：__
我的HOT博：
- New：ChatGPT初体验(ChatGPT国内镜像站初体验，聊天、Python代码生成。)CSDN质量分92。(30687阅读)
- 尼姆游戏(彩色文字界面版，\033控制码实现。Linux系统有效。)CSDN质量分xx。(1001阅读)
- 神奇的 \033 ，让打印出彩(1739阅读)
- 小炼二维数组(1764阅读)
- 仿真模拟福彩双色球(2622阅读)
- Python之魔幻切片(1417阅读)
- 数列求和a, aa, aaa, ..., aa...aa(n个a)(1729阅读)
- 个人信息提取(2671阅读)
- 中文字符命名Python变量和函数(1021阅读)
- 我的Python学习笔记(1021阅读)
- 十六进制字符串转Python代码(utf-8字符串转十六进制字符串)(1319阅读)
- 生成100个随机正整数(2489阅读)
- 给定字符串提取姓名(字符串、list、re“零宽断言”)(1842阅读)
- 我的 Python.color() (Python 色彩打印控制)(2370阅读)
- python清屏(3150阅读)
- 回车符、换行符和回车换行符(3558阅读)
- Linux 脚本文件第一行的特殊注释符(井号和感叹号组合)的含义(2301阅读)
- random.sample()将在python 3.9x后续版本中被弃用(2045阅读)
- pandas 数据类型之 Series(1809阅读)
- 聊天消息敏感词屏蔽系统(字符串替换 str.replace(str1, *) )(2332阅读)
- 练习：银行复利计算(用 for 循环解一道初中小题)(2159阅读)
- pandas 数据类型之 DataFrame(5932阅读)
- 班里有人和我同生日难吗？(蒙特卡洛随机模拟法)(2921阅读)
- Python 续行符(\)“拯救”你的超长语句(1502阅读)
- Python字符串居中显示(4684阅读)
- 练习：求偶数和、阈值分割和求差( list 对象的两个基础小题)(2331阅读)
- 用 pandas 解一道小题(2268阅读)
- 可迭代对象和四个函数(1752阅读)
- “快乐数”判断(1847阅读)
- 罗马数字转换器(构造元素取模)(3157阅读)
- Hot：罗马数字(转换器|罗生成器)(5783阅读)
- Hot：让QQ群昵称色变的代码(49777阅读)
- Hot：斐波那契数列(递归| for )(4719阅读)
- 柱状图中最大矩形(2348阅读)
- 排序数组元素的重复起止(1964阅读)
- 电话拨号键盘字母组合(2170阅读)
- 密码强度检测器(3124阅读)
- 求列表平衡点(2498阅读)
- Hot：字符串统计(4581阅读)
- Hot：尼姆游戏(聪明版首发)(4135阅读)
- 尼姆游戏(优化版)(1968阅读)
推荐条件点阅破千
回页首
精品文章：
- 好文力荐：齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
- OPP三大特性：封装中的property
- 通过内置对象理解python'
- 正则表达式
- python中“*”的作用
- Python 完全自学手册
- 海象运算符
- Python中的 `!=`与`is not`不同
- 学习编程的正确方法
来源：老齐教室
回页首
◆ Python 入门指南【Python 3.6.3】
好文力荐：
-
全栈领域优质创作者——寒佬(还是国内某高校学生)博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是学习的两大利器。
-
【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛
-
靠谱程序员的好习惯
CSDN实用技巧博文：
- 8个好用到爆的Python实用技巧
- python忽略警告
- Python代码编写规范
- Python的docstring规范（说明文档的规范写法）