当前位置: 首页 > news >正文

备战蓝桥杯---贪心刷题1

话不多说,直接看题:

本质是一个数学题:

我们令xi<0表示反方向传递,易得我们就是求每一个xi的绝对值之和min,我们令平均值为a爸。

易得约束条件:

x1-x2=a1-a,x2-x3=a2-a.....

解得x1=x1-0,x2=x1-((n-1)*a-a2-...an)。。。。

这样就把问题转化成|x1-c1|+|x2-c2|+|...|....

又ci=ci+1+a-ai我们就可以吧c解出来,下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
long long n,a[N];
long long sum=0;
long long c[N];
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];}long long av=sum/n;for(int i=n;i>1;i--){c[i]=c[i+1]+av-a[i];}c[1]=0;sort(c+1,c+n+1);long long res=0;for(int i=1;i<=n;i++) res+=abs(c[i]-c[(i+1)/2]);cout<<res;
}

接题:

先转换一下,我们从小岛的角度来看,看看每一个小岛可以被覆盖在x轴上对应的范围,这样问题就转换成了给定若干个区间,最少选多少个点可以使得每一个区间至少选了一个点。

如何贪心?我们先按照右端点排序,扫描每一个线段,若上一个右端点不在区间,那么选右端点。

若在则跳过。

如何严格证明?

我们记cnt为算法得到的结果,opt为最优解。

显然选了cnt个,那么就有cnt个互不相交的区间,因此答案一定大于等于cnt+opt是最优解,得证!

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,d;
struct node{double l,r;
}seg[N];
bool cmp(node a,node b){return a.r<b.r;
}
int main(){cin>>n>>d;bool ff=0;for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);if(y>d) ff=1;else{double ck=sqrt(d*d-y*y);seg[i].l=x-ck,seg[i].r=x+ck;}}if(ff) cout<<-1<<endl;else{sort(seg,seg+n,cmp);int cnt=0;double last=-1000000000;for(int i=0;i<n;i++){if(last<seg[i].l){cnt++;last=seg[i].r;}}cout<<cnt;}
}

接题:

很容易想到,假如每一个人的钱都比平均大,那么都取平均即可。

假如有一个人少,那么让它填满,剩下的平均分摊给大于平均的。

下面是严格的证明:

我们把方差的每一项看成xi,xi的和为0,由均值不等式知我们要让每一个数尽可能相同,假如有一个小于平均值,假设它不选满,则结果肯定变大。

因此,若a1<平均值,那么我们就取a1,后面的式子满足加起来和为s-a1,因此剩下的加起来就是s-a1-(n-1)/n*s;此时每一个取到(s-a1)/(n-1)是最优的,而若此时大于该值,那么后面的肯定也大(排过序),因此取其即可。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=500100;
int n,a[N];
int main(){long double s;scanf("%d%Lf",&n,&s);for(int i=0;i<n;i++) scanf("%d",&a[i]);sort(a,a+n);long double res=0,av=s/n;for(int i=0;i<n;i++){double cur=s/(n-i);if(a[i]<cur) cur=a[i];res+=(cur-av)*(cur-av);s-=cur;}printf("%.4Lf\n",sqrt(res/n));
}

相关文章:

备战蓝桥杯---贪心刷题1

话不多说&#xff0c;直接看题&#xff1a; 本质是一个数学题&#xff1a; 我们令xi<0表示反方向传递&#xff0c;易得我们就是求每一个xi的绝对值之和min,我们令平均值为a爸。 易得约束条件&#xff1a; x1-x2a1-a,x2-x3a2-a..... 解得x1x1-0,x2x1-((n-1)*a-a2-...an)。…...

《数据结构学习笔记---第九篇》---循环队列的实现

文章目录 1.循环队列的定义 2.循环队列的判空判满 3.创建队列并初始化 4.入队和出队 5. 返回队尾队首元素 6.释放循环队列 1.循环队列的定义 定义&#xff1a;存储队列元素的表从逻辑上被视为一个环。 我们此次实现的循环队列&#xff0c;采用顺序表 typedef struct {int…...

前端调试工具之Chrome Elements、Network、Sources、TimeLine调试

常用的调试工具有Chrome浏览器的调试工具&#xff0c;火狐浏览器的Firebug插件调试工具&#xff0c;IE的开发人员工具等。它们的功能与使用方法大致相似。Chrome浏览器简洁快速&#xff0c;功能强大这里主要介绍Chrome浏览器的调试工具。 打开 Google Chrome 浏览器&#xff0c…...

vue 加 websocket 聊天

<template><div style="height: 100%; width: 100%; background-color: #fff"><div class="wrap"><!-- 头部 --><div class="titleBox"><imgsrc="@/assets/image/avatar.png"style="argin: 10p…...

uniapp通过蓝牙传输数据 (ios)

在uni-app中&#xff0c;可以通过uni-ble&#xff08;uni-app官方提供的蓝牙插件&#xff09;来实现iOS设备上的蓝牙数据传输。 首先&#xff0c;确保已在uni-app的manifest.json文件中添加uni-ble插件的配置&#xff1a; "permission": { "scope.userLocati…...

docker搭建CI/CD环境配置过程中的常见问题

一、Jenkins 1、pull镜像问题 docker pull jenkins/jenkins:lts Using default tag: latest Trying to pull repository docker.io/library/centos ... Get https://registry-1.docker.io/v2/library/centos/manifests/latest: Get https://auth.docker.io/token?scoperepo…...

实验四 微信小程序智能手机互联网程序设计(微信程序方向)实验报告

请编写一个用户登录界面&#xff0c;提示输入用户名和密码进行登录&#xff1b; 代码 index.wxml <view class"user"> <form bindreset""> <view>用户名&#xff1a;</view><input type"text"name""/>…...

WPF —— 关键帧动画

wpf动画类型 1<类型>Animation这些动画称为from/to/by动画或者叫基本动画&#xff0c;他们会在起始值或者结束值进行动画处理&#xff0c;常用的例如 <DoubleAnimation> 2 <类型>AnimationUsingKeyFrames: 关键帧动画&#xff0c;功能要比from/to这些动画功…...

Taro + vue3 小程序封装标题组件

分为没有跳转页面的title组件和 有跳转页面的title组件 我们可以把这个封装成一个组件 直接上代码 <template><div class"fixed-title-container"><div class"box"><div class"icon" v-if"isShow" click"…...

babyAGI(6)-babyCoder源码阅读2任务描述部分

废话不多说&#xff0c;我们直接看task的prompt 这里需要注意的是&#xff0c;每个openai_call的temperature都不相同&#xff0c;这也是开发程序时需要调整和关注的一点 1. 初始化代码任务agent 作为babycoder的第一个angent&#xff0c;整个prompt编写的十分值得学习 整个p…...

生成式语言模型预训练阶段验证方式与微调阶段验证方式

生成式语言模型&#xff0c;如GPT-3、BERT等&#xff0c;在预训练和微调阶段都需要进行验证以确保模型性能。下面分别介绍这两个阶段的验证方式&#xff1a; 预训练阶段的验证&#xff1a; 预训练阶段通常使用大量未标注的文本数据来训练模型&#xff0c;以学习语言的一般特性。…...

flink on yarn

前言 Apache Flink&#xff0c;作为大数据处理领域的璀璨明星&#xff0c;以其独特的流处理和批处理一体化模型&#xff0c;成为众多企业和开发者的首选。它不仅能够在处理无界数据流时展现出卓越的实时性能&#xff0c;还能在有界数据批处理上达到高效稳定的效果。本文将简要…...

用TOMCAT部署web项目教程

文章目录 引言I 使用webapps文件夹II 利用server.xmlIII 自定义配置文件IV 预备知识4.1项目的一般结构4.2 contex标签4.3 IDE部署4.4 配置Tomcat服务引言 在开发阶段,一般使用IDE如MyEclipse来部署web项目,不要忘记手动部署的三种方式。 I 使用webapps文件夹 将项目文件夹…...

bash例子-source进程替换、alias不生效处理

#1. source 例子&#xff0c; 进程替换source <(echo alias zls"ls") #上一行 中 echo替换为cat&#xff0c;则得到如下行, 好处是 cat不用处理引号转义问题&#xff0c;而echo则必须处理引号转义问题#写一段复杂脚本&#xff0c;且 不处理引号转义问题 &#x…...

rabbitmq死信交换机,死信队列使用

背景 对于核心业务需要保证消息必须正常消费&#xff0c;就必须考虑消费失败的场景&#xff0c;rabbitmq提供了以下三种消费失败处理机制 直接reject&#xff0c;丢弃消息&#xff08;默认&#xff09;返回nack&#xff0c;消息重新入队列将失败消息投递到指定的交换机 对于核…...

gitlab备份与恢复

1.1.1 查看系统版本和软件版本 cat /etc/debian_version cat /opt/gitlab/embedded/service/gitlab-rails/VERSION 1.1.2 数据备份 打开/etc/gitlab/gitlab.rb配置文件&#xff0c;查看一个和备份相关的配置项 sudo vim /etc/gitlab/gitlab.rb gitlab_rails[backup_path] &q…...

HBase详解(1)

HBase 简介 概述 HBase是Yahoo!公司开发的后来贡献给了Apache的一套开源的、分布式的、可扩展的、基于Hadoop的非关系型数据库(Non-Relational Database)&#xff0c;因此HBase并不支持SQL(几乎所有的非关系型数据库都不支持SQL)&#xff0c;而是提供了一套单独的命令和API操…...

深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度

看这篇前请先把我上一篇了解一下&#xff1a;深入理解数据结构第一弹——二叉树&#xff08;1&#xff09;——堆-CSDN博客 前言&#xff1a; 相信很多学习数据结构的人&#xff0c;都会遇到一种情况&#xff0c;就是明明最一开始学习就学习了时间复杂度&#xff0c;但是在后期…...

视频汇聚/安防监控/EasyCVR平台播放器EasyPlayer更新:新增【性能面板】

视频汇聚/安防监控/视频存储平台EasyCVR基于云边端架构&#xff0c;可以在复杂的网络环境中快速、灵活部署&#xff0c;平台视频能力丰富&#xff0c;可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集中存储、云…...

【教程】Flutter 应用混淆

在移动应用开发中&#xff0c;保护应用代码安全至关重要。Flutter 提供了简单易用的混淆工具&#xff0c;帮助开发者在构建 release 版本应用时有效保护代码。本文将介绍如何在 Flutter 应用中使用混淆&#xff0c;并提供了相关的操作步骤和注意事项。 &#x1f4dd; 摘要 本…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...