[Daimayuan] 吃糖果(C++,贪心)

news/2024/2/28 2:03:11

桌子上从左到右放着 n n n 个糖果。糖果从左到右编号,第 i i i 块糖果的重量为 w i w_i wi。小明和小红要吃糖果。

小明从左边开始吃任意数量的糖果。(连续吃,不能跳过糖果)

小红从右边开始吃任意数量的糖果。(连续吃,不能跳过糖果)

当然,如果小明吃了某个糖果,小红就不能吃它(反之亦然)。

他们的目标是吃同样重量的糖果,请问此时他们总共最多能吃多少个糖果?

输入格式

第一行包含一个整数 n n n,表示桌上糖果的数量。

第二行包含 n n n 个整数 w 1 , w 2 , … , w n w_1,w_2,…,w_n w1,w2,,wn,表示糖果从左到右的重量。

输出格式

一个整数,表示小明和小红在满足条件的情况下总共可以吃的糖果的最大数量。

数据范围

1 ≤ n ≤ 2 ∗ 1 0 5 , 1 ≤ w i ≤ 1 0 4 1≤n≤2*10^5,1≤w_i≤10^4 1n2105,1wi104

输入样例

9
7 3 20 5 15 1 11 8 10

输出样例

7

解题思路

采用贪心算法(不断尝试吃更多的糖)解决此题:

初始化规定糖的重量相等,然后循环分支:

(1)糖的重量相等,记录当前总共吃了多少颗糖,双方再吃一颗糖;

(2)糖的重量不相等,吃的少的一方再吃一颗糖。

结束条件:双方吃糖发生冲突(题目规定:“如果小明吃了某个糖果,小红就不能吃它(反之亦然)”)。

AC代码如下:

#include <iostream>
using namespace std;
const int max_n = 2e5;
const int max_w = 1e4;int candies[max_n];int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> candies[i];int l = 0, r = n - 1, l_sum = 0, r_sum = 0, ans = 0;while (l < r) {if (l_sum == r_sum) {ans = l - 0 + n - 1 - r;l_sum += candies[l++];r_sum += candies[r--];}else if (l_sum < r_sum) l_sum += candies[l++];else r_sum += candies[r--];}cout << ans << endl;return 0;
}

贪心证明:

初始化,规定双方吃糖量相同,吃糖数目为 0 0 0

为了确定是否存在比 0 0 0大的解,我们必须要让其中一方吃一颗糖。

那么这就会导致双方吃糖量不等,要让其相等,我们必须让另一方吃一颗糖。

只要不平衡,我们就需要让吃的少的那一方继续吃。

当平衡的时候,设吃糖数目为 a n s ans ans

为了确定是否存在比 a n s ans ans大的解,我们必须要让其中一方吃一颗糖…(依次类推,直到发生冲突)


http://www.ppmy.cn/news/52352.html

相关文章

全光谱防蓝光护眼灯有用吗?怎么分辨是全光谱灯

每个人的家里都有一两个台灯&#xff0c;孩子用来学习&#xff0c;老人用来阅读。但台灯不仅仅是用来照明而已&#xff0c;还需要呵护我们的双眼。现在的孩子患近视的人越来越多&#xff0c;很多小学生都戴上了眼镜&#xff0c;而老年人老花眼白内障的患者也在攀升&#xff0c;…

onnx笔记2:onnx操作实例

1. 介绍 本文以yolov5s模型,演示对yolov5s.onnx模型文件的读取,修改等操作 2. onnx操作 2.1 获取数据 (1) 案例1 :读取weights数据 比如获取yolov5s.onnx第一个Conv的weights数据。 点击左侧第一个Conv, 右侧INPUTS下面的W点开+号,可以看到该Conv的weight的name为m…

udev mdev热插拔配置说明

udev mdev热插拔配置说明 udev udev介绍 udev用于linux2.6.13或更高版本的内核上&#xff0c;为用户空间提供使用固定设备名的动态/dev目录的解决方案。它通过在 sysfs 的 /class/ 和/block/ 目录树中查找一个称为 dev 的文件&#xff0c;以确定所创建的设备节点文件的主次设…

CSS3小可爱亲吻表白特效,给你的五一假期增添点小乐趣

马上五一假期了&#xff0c;小伙伴们是不是都准备出去旅游呢&#xff0c;或者回老家陪陪父母。今天我用CSS3制作一个小可爱亲吻表白的特效&#xff0c;来给你即将到来的五一假期增添点小小的乐趣。 目录 实现思路 左边小可爱的实现 右边小可爱的实现 左右摇摆动效的实现 右…

js截取网址参数值方法

一般分为两种网址截取方法&#xff1a; 第一种&#xff0c;例如链接&#xff1a;http://192.168.32.135:9020/#/authentication/Login?toeknceshi token 值出现在 URL 的 hash 部分,所以你需要使用 window.location.hash 来获取 hash 部分&#xff0c;然后使用 URLSearchPara…

API 都有这些功能,你真的都知道么?

API&#xff08;应用程序编程接口&#xff09;可以提供以下功能&#xff1a; 数据传输&#xff1a;API可以在应用程序之间传输数据&#xff0c;包括发送和获取数据、更新数据等。 访问功能: API 可以调用另一个系统或应用程序的某些功能&#xff0c;例如获取天气&#xff0c;查…

PXE 网络安装Linux ——Kickstart无人值守安装Linux

PXE&#xff08;预启动执行环境&#xff09; PXE&#xff08;预启动执行环境&#xff09; 由Intel公司开发的网络引导技术&#xff0c;工作在Client/Server模式&#xff0c;允许客户机通过网络从远程服务器下载引导镜像&#xff0c;并加载安装文件或者整个操作系统。 PXE具备以…

Oracle Linux 9 上基于 Docker 安装 Kubernetes 1.27 集群

Oracle Linux 9 上基于 Docker 安装 Kubernetes 1.27 集群 1. 禁用swap2. 禁用防火墙3. 将SELinux设置为permissive模式4. 添加网桥过滤及内核转发配置文件5. 加载 overlay、br_netfilter、ip_tables、iptable_filter 模块6. 安装 docker-ce7. 安装kubelet kubeadm kubectl8. 初…

力扣刷题——移除元素

1、移除元素 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中…

不部署服务端调用接口,前端接口神器json-server

简介 json-server 是一款小巧的接口模拟工具&#xff0c;一分钟内就能搭建一套 Restful 风格的 API&#xff0c;尤其适合前端接口测试使用。 只需指定一个 json 文件作为 api 的数据源即可&#xff0c;使用起来非常方便&#xff0c;30秒入门&#xff0c;基本上有手就行。 进阶…

JS笔试题精讲3 ES6专题

只要拼接字符串 一律用 模板字符串 ${} 里: - 可以放: 变量、算术计算、三目、对象属性、创建对象、调用 函数、访问数组元素——有返回值的合法的js表达式 - 不能放: 没有返回值的js表达式也不能放分支/判断、循环等程序结构。比如: if else for while...等 ${}规则和今后…

如何使用ESP32-CAM构建一个人脸识别系统

有许多人识别系统使用签名、指纹、语音、手部几何、人脸识别等来识别人&#xff0c;但除了人脸识别系统。 人脸识别系统不仅可以用于安全目的来识别公共场所的人员&#xff0c;还可以用于办公室和学校的考勤目的。 在这个项目中&#xff0c;我们将使用 ESP32-CAM 构建一个人脸识…

零售库存管理系统该如何选?这5款零售库存管理系统值得推荐!

对于实体门店来说&#xff0c;做零售就是做库存&#xff0c;谁能及时把店内的库存清空&#xff0c;谁就能快速盈利&#xff0c;这就需要实体门店能够简单高效的管理好库存。 但很多实体店基本上没有足够的人手和实力去制定科学的库存管理策略&#xff0c;借助零售库存管理系统&…

Java题目训练——不用加减乘除做加法和三角形

目录 一、不用加减乘除做加法 二、三角形 一、不用加减乘除做加法 题目描述&#xff1a; 写一个函数&#xff0c;求两个整数之和&#xff0c;要求在函数体内不得使用、-、*、/四则运算符号。 数据范围&#xff1a;两个数都满足 -10<n<1000 进阶&#xff1a;空间复杂度…

Beta成果测试总结

Beta成果测试总结 Beta是一个项目的早期测试&#xff0c;通过 Beta能够初步的了解整个系统的稳定性&#xff0c;测试系统是否能够满足客户的需求。我们可以在测试过程中发现一些问题&#xff0c;从而快速解决。 当我们在测试一个新系统时&#xff0c;我们需要进行测试前的准备工…

部署LVS-DR 集群及实验

一、LVS-DR工作原理 LVS-DR&#xff08;Linux Virtual Server Director Server&#xff09;工作模式&#xff0c;是生产环境中最常用的一种工作模式。 #①LVS-DR 模式&#xff0c;Director Server 作为群集的访问入口&#xff0c;不作为网关使用&#xff1b; #②节点 Directo…

Node实现CSDN博客导出(后续)

前言 在2021年我实现了一个Node导出博客的功能&#xff1a;爬取接口及博客页面并导出为md文件格式。中途有许多迭代及优化以及解决了一些关键问题&#xff0c;写篇文章做个记录和review 博客更新功能 在原有的导出功能上增加了博客更新的功能&#xff0c;避免了每次都全部导…

Raft 共识算法1-Raft基础

Raft 共识算法1-Raft基础 Raft算法中译版地址&#xff1a;http://www.redisant.cn/etcd/contact 英原论文地址&#xff1a;https://raft.github.io/raft.pdf Etcd Assistant 是一款 etcd 可视化管理软件&#xff0c;便捷高效地操作您的 etcd 集群&#xff1b;支持多种键的视图&…

数字未来:世界正走向新的“破茧时刻”

著名科学史专家亚历山大柯瓦雷&#xff0c;在《从封闭世界到无限宇宙》展示了一段非常神奇的历史现象&#xff1a;人类从笃信自己生活在一个封闭空间&#xff0c;到认识浩瀚无垠的宇宙&#xff0c;其实并没有耗费很长时间。自1543年哥白尼发布《天体运行论》&#xff0c;到牛顿…

基于PWM技术的三相光伏逆变器研究(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
最新文章