备战蓝桥杯---贪心刷题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));
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/511242.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

硬件了解 笔记

motherboard的高低端区别在哪里&#xff1f; 核心&#xff1a;从单核变成双核&#xff0c;多核&#xff08;几核就是几个打工人&#xff09; 多线程&#xff1a;6核本来对应6个线程&#xff0c;但是多线程就是说6核对应12个线程 频率 主频&#xff1a;平时打工的速度 睿频&…

达梦数据库 优化

谁进行优化&#xff1f;优化什么&#xff1f; 优化不能仅从数据库方面考虑&#xff0c;比如&#xff0c;在存储达到数据库极限、应用涉及人员设计的代码稀巴烂的情况下&#xff0c;进行调优就是杯水车薪的效果。 涉及到优化人员&#xff1a; 数据库管理员应用程序架构师应用…

Javascript/Node.JS中如何用多种方式避免属性为空(cannot read property of undefined ERROR)

>>>>>>问题 "cannot read property of undefined" 是一个常见的 JavaScript 错误&#xff0c;包含我在内很多人都会遇到&#xff0c;表示你试图访问一个未定义&#xff08;undefined&#xff09;对象的属性。这通常是因为你在访问一个不存在的对象…

制造型企业实施WMS仓储管理系统前后的变化

在科技浪潮的推动下&#xff0c;WMS仓储管理系统逐渐崭露头角&#xff0c;成为制造企业优化运营、提升竞争力的得力助手。本文将从制造企业实施WMS仓储管理系统前后的对比入手&#xff0c;探讨这一变革所带来的深远影响。 一、WMS仓储管理系统实施前的仓储管理挑战 在WMS仓储管…

【LeetCode: 96. 不同的二叉搜索树 + 动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

从0到1完成UI自动化测试框架搭建之Pytest

上篇文章中&#xff0c;我们学会了如何使用UI Automator2atx编写简单的Android自动化脚本。 但是有个问题&#xff0c;大家可以思考下&#xff0c;光用自动化脚本让它自己动起来&#xff0c;是不是缺了点什么&#xff1f; 我们写测试用例的时候&#xff0c;是不是经常写&…

redis 的StringRedisTemplate

6.3 StringRedisTemplate 尽管JSON的序列化方式可以满足我们的需求&#xff0c;但依然存在一些问题&#xff0c;如图&#xff1a; 为了在反序列化时知道对象的类型&#xff0c;JSON序列化器会将类的class类型写入json结果中&#xff0c;存入Redis&#xff0c;会带来额外的内存…

透彻理解二分查找-算法通关村

透彻理解二分查找-算法通关村 常见的查找算法有顺序查找、二分查找、插值查找&#xff0c;树表查找、分块查找、哈希查找等等。其实二分查找、插值查找以及斐波那契查找都可以归为一类—插值查找。插值查找是在二分查找的基础上的优化查找算法。 二分查找的价值&#xff0c;请…

大数据分析与内存计算——Spark安装以及Hadoop操作——注意事项

一、Spark安装 1.相关链接 https://dblab.xmu.edu.cn/blog/4322/ 2.安装Spark&#xff08;Local模式&#xff09; 按照文章中的步骤安装即可 遇到问题&#xff1a;xshell以及xftp不能使用 解决办法&#xff1a; 在linux使用镜像网站进行下载&#xff1a;wget https://mi…

Three.js真实相机模拟

有没有想过如何在 3D Web 应用程序中模拟物理相机&#xff1f; 在这篇博文中&#xff0c;我将向你展示如何使用 Three.js和 OpenCV 来完成此操作。 我们将从模拟针孔相机模型开始&#xff0c;然后添加真实的镜头畸变。 具体来说&#xff0c;我们将仔细研究 OpenCV 的两个失真模…

【Java 集合进阶】单练集合顶层接口collction迭代器

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏 …

适合初学者的Linux的综合项目

大家好&#xff0c;今天给大家介绍适合初学者的Linux的综合项目&#xff0c;文章末尾附有分享大家一个资料包&#xff0c;差不多150多G。里面学习内容、面经、项目都比较新也比较全&#xff01;可进群免费领取。 对于初学者来说&#xff0c;Linux的综合项目应当既具有教育意义又…

element plus 输入框样式模仿Material-UI

获取焦点状态 自定义指令 app.directive(focus, { // 当被绑定的元素插入到 DOM 中时…… mounted(el) { const descendants el.querySelectorAll(.el-input__inner); var cssClass newLable;el.classList.add(cssClass); // 遍历并操作这些子孙节点 descendants.forE…

(24年4月2日更新)Linux安装chrome及chromedriver(Ubuntu20.0416.04)

一、安装Chrome 1&#xff09;先执行命令下载chrome&#xff1a; wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb2&#xff09;安装chrome sudo dpkg -i google-chrome-stable_current_amd64.deb踩坑&#xff1a;这里会提示如下报错&…

安卓主板MT8390(Genio 700)_MTK联发科Linux开发板方案

MediaTek Genio 700 &#xff08;MT8390&#xff09;是一款高性能的边缘 AI 物联网平台&#xff0c;专为智能家居、互动零售、工业与商业应用而设计。提供快速响应的边缘计算能力、先进的多媒体功能、广泛的传感器和连接方式&#xff0c;且支持多任务操作系统。 MT8390安卓核心…

ArrayList扩容原理

ArrayList源码分析 分析ArrayList源码主要从三个方面去翻阅&#xff1a;成员变量&#xff0c;构造函数&#xff0c;关键方法 以下源码都来源于jdk1.8 1 成员变量 DEFAULT_CAPACITY 10; 默认初始的容量**(CAPACITY) EMPTY_ELEMENTDATA {}; 用于空实例的共享空数组实例 DEFAU…

Java项目:85 springboot智能物流管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本美发门店管理系统有管理员和用户两个角色。 用户功能有项目预定管理&#xff0c;产品购买管理&#xff0c;会员充值管理&#xff0c;余额查询管理。…

文本自动粘贴编辑器:支持自动粘贴并筛选手机号码,让信息处理更轻松

在信息时代的浪潮中&#xff0c;文本处理已成为我们日常工作与生活的重要组成部分。无论是商务沟通、社交互动还是个人事务处理&#xff0c;手机号码的筛选与粘贴都显得尤为关键。然而&#xff0c;传统的文本处理方式效率低下、易出错&#xff0c;已无法满足现代人的高效需求。…

Linux(05) Debian 系统修改主机名

查看主机名 方法1&#xff1a;hostname hostname 方法2&#xff1a;cat etc/hostname cat /etc/hostname 如果在创建Linux系统的时候忘记修改主机名&#xff0c;可以采用以下的方式来修改主机名称。 修改主机名 注意&#xff0c;在linux中下划线“_”可能是无效的字符&…

disearch目录扫描工具

项目地址 GitHub - maurosoria/dirsearch: Web path scanner 安装 apt-get install dirsearch 使用 dirsearch -u http://61.147.171.105:56237/