帮我用c语言实现 题目描述 小K同学有一箱袜子,这些袜子各自有着不同的图案,并且有的袜子只能左脚穿、有的袜子只能右脚穿、还有的袜子左右脚都能穿。每天早上他都必须从箱子里拿出1对配套的袜子穿着出门(配套的袜子必须是图案相同的,并且左脚和右脚各有1只可以穿得上的袜子)。现在告诉你箱子里本质不同(图案不同或者左右脚适配性不同)的袜子各有多少只,小K同学想知道,他最少要从箱子里取出多少只袜子,才可以保证凑齐至少1对配套的袜子? 输入描述: 第一行输入一个正整数N,表示有多少种本质不同的袜子; 接下来的N行,每行输入P,Q,M,其中P是一个非负整数,表示袜子的图案;Q是一个字符,当Q取值为'L'时,表示袜子只适配左脚,当Q取值为'R'时,表示袜子只适配右脚,当Q取值为'*'时,表示袜子同时适配左右脚;M是一个正整数,表示这种袜子共有多少只。 (1<=N<=10^5,0<=P<=10^9,Q ∈ { 'L' , 'R' ,'*'},1<=M<=10^5) 输出描述: 对于每组测试数据,输出1个答案,表示最少取出的袜子数。若无法配对成功,输出-1。 示例1 输入 3 0 L 7 0 R 3 1 * 10 输出 9 说明 取出7只图案为0的左脚袜子,取出1只图案为0的右脚袜子,再取出1只图案为1的袜子。

时间: 2023-05-19 16:02:54 浏览: 54
这是一个经典的贪心问题,我们可以按照以下步骤解决: 1. 统计左脚、右脚和双脚袜子的数量。 2. 对于每一种图案,分别计算左脚、右脚和双脚袜子的数量。 3. 对于每一种图案,取左脚和右脚袜子数量的较小值,加起来就是这种图案最少需要取出的袜子数量。 4. 对于所有图案,将它们最少需要取出的袜子数量相加,就是总共需要取出的袜子数量。 5. 如果总共需要取出的袜子数量大于箱子里所有袜子的数量之和,说明无法配对成功,输出-1,否则输出总共需要取出的袜子数量。 下面是C语言的实现代码: #include <stdio.h> #include <string.h> #define MAXN 100000 struct Sock { int pattern; int left; int right; int both; }; int main() { int n, i, j; struct Sock socks[MAXN]; int cnt_left = 0, cnt_right = 0, cnt_both = 0; int cnt_pattern[MAXN] = {0}; int cnt_pattern_left[MAXN] = {0}; int cnt_pattern_right[MAXN] = {0}; int cnt_pattern_both[MAXN] = {0}; int ans = 0; scanf("%d", &n); for (i = 0; i < n; i++) { int pattern, m; char q; scanf("%d %c %d", &pattern, &q, &m); socks[i].pattern = pattern; if (q == 'L') { socks[i].left = m; cnt_left += m; cnt_pattern_left[pattern] += m; } else if (q == 'R') { socks[i].right = m; cnt_right += m; cnt_pattern_right[pattern] += m; } else { socks[i].both = m; cnt_both += m; cnt_pattern_both[pattern] += m; } cnt_pattern[pattern] += m; } for (i = 0; i < n; i++) { int min_cnt = cnt_pattern_left[socks[i].pattern]; if (cnt_pattern_right[socks[i].pattern] < min_cnt) { min_cnt = cnt_pattern_right[socks[i].pattern]; } if (cnt_pattern_both[socks[i].pattern] < min_cnt) { min_cnt = cnt_pattern_both[socks[i].pattern]; } ans += min_cnt; } if (ans * 2 > cnt_left + cnt_right + cnt_both) { printf("-1\n"); } else { printf("%d\n", ans); } return 0; }

最新推荐

recommend-type

c语言实现输入一组数自动从大到小排列的实例代码

下面小编就为大家带来一篇c语言实现输入一组数自动从大到小排列的实例代码。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
recommend-type

在C语言中输入一个大写字母,将其转变成一个小写字母,并且有相应的提示。

1.学习简单的C语言编程
recommend-type

C语言实现小型电子词典

C语言实现小型电子词典 本文主要介绍了使用C语言实现小型电子词典的过程,用户可以进行英译汉、汉译英等功能,具有一定的参考价值。 一、词典系统的设计 在设计小型电子词典时,需要考虑到用户的需求和词典的存储...
recommend-type

使用C语言实现CRC校验的方法

CRC(Cyclic Redundancy Check,循环冗余...不同的CRC码有不同的生成多项式,选择合适的CRC码可以满足不同应用场景的需求。在实际开发中,理解CRC的基本原理和C语言实现方式对于正确实现和调试CRC校验功能至关重要。
recommend-type

C语言利用EasyX实现图形化界面的小游戏

C语言利用EasyX库实现图形化界面的小游戏是一种将低级语言与图形化结合的方法,适合初学者加深对C语言的理解并实践。EasyX是一个为C/C++设计的简单图形库,它提供了丰富的图形绘制函数,使得开发者能够轻松地在...
recommend-type

BSC关键绩效财务与客户指标详解

BSC(Balanced Scorecard,平衡计分卡)是一种战略绩效管理系统,它将企业的绩效评估从传统的财务维度扩展到非财务领域,以提供更全面、深入的业绩衡量。在提供的文档中,BSC绩效考核指标主要分为两大类:财务类和客户类。 1. 财务类指标: - 部门费用的实际与预算比较:如项目研究开发费用、课题费用、招聘费用、培训费用和新产品研发费用,均通过实际支出与计划预算的百分比来衡量,这反映了部门在成本控制上的效率。 - 经营利润指标:如承保利润、赔付率和理赔统计,这些涉及保险公司的核心盈利能力和风险管理水平。 - 人力成本和保费收益:如人力成本与计划的比例,以及标准保费、附加佣金、续期推动费用等与预算的对比,评估业务运营和盈利能力。 - 财务效率:包括管理费用、销售费用和投资回报率,如净投资收益率、销售目标达成率等,反映公司的财务健康状况和经营效率。 2. 客户类指标: - 客户满意度:通过包装水平客户满意度调研,了解产品和服务的质量和客户体验。 - 市场表现:通过市场销售月报和市场份额,衡量公司在市场中的竞争地位和销售业绩。 - 服务指标:如新契约标保完成度、续保率和出租率,体现客户服务质量和客户忠诚度。 - 品牌和市场知名度:通过问卷调查、公众媒体反馈和总公司级评价来评估品牌影响力和市场认知度。 BSC绩效考核指标旨在确保企业的战略目标与财务和非财务目标的平衡,通过量化这些关键指标,帮助管理层做出决策,优化资源配置,并驱动组织的整体业绩提升。同时,这份指标汇总文档强调了财务稳健性和客户满意度的重要性,体现了现代企业对多维度绩效管理的重视。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。

![【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/70a49cc62dcc46a491b9f63542110765~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp) # 1. 俄罗斯方块游戏概述** 俄罗斯方块是一款经典的益智游戏,由阿列克谢·帕基特诺夫于1984年发明。游戏目标是通过控制不断下落的方块,排列成水平线,消除它们并获得分数。俄罗斯方块风靡全球,成为有史以来最受欢迎的视频游戏之一。 # 2.
recommend-type

卷积神经网络实现手势识别程序

卷积神经网络(Convolutional Neural Network, CNN)在手势识别中是一种非常有效的机器学习模型。CNN特别适用于处理图像数据,因为它能够自动提取和学习局部特征,这对于像手势这样的空间模式识别非常重要。以下是使用CNN实现手势识别的基本步骤: 1. **输入数据准备**:首先,你需要收集或获取一组带有标签的手势图像,作为训练和测试数据集。 2. **数据预处理**:对图像进行标准化、裁剪、大小调整等操作,以便于网络输入。 3. **卷积层(Convolutional Layer)**:这是CNN的核心部分,通过一系列可学习的滤波器(卷积核)对输入图像进行卷积,以
recommend-type

绘制企业战略地图:从财务到客户价值的六步法

"BSC资料.pdf" 战略地图是一种战略管理工具,它帮助企业将战略目标可视化,确保所有部门和员工的工作都与公司的整体战略方向保持一致。战略地图的核心内容包括四个相互关联的视角:财务、客户、内部流程和学习与成长。 1. **财务视角**:这是战略地图的最终目标,通常表现为股东价值的提升。例如,股东期望五年后的销售收入达到五亿元,而目前只有一亿元,那么四亿元的差距就是企业的总体目标。 2. **客户视角**:为了实现财务目标,需要明确客户价值主张。企业可以通过提供最低总成本、产品创新、全面解决方案或系统锁定等方式吸引和保留客户,以实现销售额的增长。 3. **内部流程视角**:确定关键流程以支持客户价值主张和财务目标的实现。主要流程可能包括运营管理、客户管理、创新和社会责任等,每个流程都需要有明确的短期、中期和长期目标。 4. **学习与成长视角**:评估和提升企业的人力资本、信息资本和组织资本,确保这些无形资产能够支持内部流程的优化和战略目标的达成。 绘制战略地图的六个步骤: 1. **确定股东价值差距**:识别与股东期望之间的差距。 2. **调整客户价值主张**:分析客户并调整策略以满足他们的需求。 3. **设定价值提升时间表**:规划各阶段的目标以逐步缩小差距。 4. **确定战略主题**:识别关键内部流程并设定目标。 5. **提升战略准备度**:评估并提升无形资产的战略准备度。 6. **制定行动方案**:根据战略地图制定具体行动计划,分配资源和预算。 战略地图的有效性主要取决于两个要素: 1. **KPI的数量及分布比例**:一个有效的战略地图通常包含20个左右的指标,且在四个视角之间有均衡的分布,如财务20%,客户20%,内部流程40%。 2. **KPI的性质比例**:指标应涵盖财务、客户、内部流程和学习与成长等各个方面,以全面反映组织的绩效。 战略地图不仅帮助管理层清晰传达战略意图,也使员工能更好地理解自己的工作如何对公司整体目标产生贡献,从而提高执行力和组织协同性。