[BZOJ 3477] [Usaco2014 Mar Gold] Sabotage

news/2024/4/20 18:30:51/

金组的神题喵。。

[题目描述]

  给你N个数,第一个和最后一个不能去掉。

现希望去掉中间某段连续的数,使得剩下的数的平均值最小化。



之前已经做了很久,一直想不到正解。。然后去网上查,发现没有。。

又去USACO上看官方题解,发现看不懂喵。。

然后很绝望地问了杜教。。

结果杜教很鄙视地只回了一句话。。


然后我就很不知天高地厚地D了杜教


后来杜教再很无奈地


哎。。。。。

妈蛋自己之前只想着二分长度什么的。。没想到二分答案

哎自己这么弱连杜教都拯救不了自己。。

这么弱搞什么OI。。


那么接下来给出一个正式的题解。。

       二分答案,然后对于每一个Ai-=c

       对这个序列的第2项到第n-1项求最长字串。。

      设这个值是max,那么可以得到 max+x(即前面的那一段的和)+y(即后面的那一段和)=all-c*n,all是原数列和

       x+y=all-ans*n-max

       如果x+y<=0,那么这个c就是合法的。。

      完毕。。

[反思]

          其实之前想的和这个很相近,只是没有往二分上想。。

          知识运用不够灵活。。

         而且之前推到出来的公式和上面的差不多,就想着怎么让x+y最小,,就想出了很多神奇搞法。。

Code:

const shuru='sabota.in';shuchu='sabota.out';maxn=100000;INF=1 shl 25;
var	a:array[0..maxn] of longint;b:array[0..maxn] of extended;step,all,i,j,k,n:longint;mid,p,data,ans,left,right:extended;
function big(a,b:longint):longint;
beginif a>b then exit(a);exit(b);
end;
procedure init;
beginreadln(n);for i:=1 to n do begin readln(a[i]); inc(all,a[i]); step:=big(step,a[i]); end;
end;
function max(a,b:extended):extended;
beginif a>b then exit(a);exit(b);
end;
function min(a,b:extended):extended;
beginif a<b then exit(a);exit(b);
end;
function gotmax:extended;
var i:longint;ans:extended;
begingotmax:=0;ans:=-INF;for i:=2 to n-1 dobegingotmax:=gotmax+b[i]; ans:=max(ans,gotmax);if gotmax<0 then gotmax:=0;end;exit(ans);
end;
procedure main;
begininit;left:=0;right:=step;ans:=INF;repeatmid:=(left+right)/2;for i:=1 to n do b[i]:=a[i]-mid;data:=gotmax;p:=all-mid*n-data;if p<=0 then beginright:=mid-0.0000001;ans:=min(ans,mid);endelse left:=mid+0.0000001;until right-left<0.00001;if ans=INF then writeln(2.000:0:3)else writeln(Ans:0:3);
end;
beginmain;
end.


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

相关文章

7744

aabb问题 1.简单的计算 #include<stdio.h> #include<math.h> int main(){int a, b, n;double m;for(a 1; a < 9; a){for(b 0; b < 9; b){n a * 1100 b * 11;m sqrt(n);if(floor(m 0.5) m){printf("%d\n",n);}}}return 0; } 2.枚举 #includ…

hdu3714

/* 分析&#xff1a; 三分。 每个F(x)都是这n个函数、在这一个x点的、最大值&#xff0c; 求F[x]在[0,1000]内的最小值。 2012-10-08 */ #include"stdio.h" #include"string.h" #include"stdlib.h" #include"math.h" #define e 1e-9 i…

Egg 中间件使用详解

1. 自定义中间件全局配置 1. 在 middleware 文件夹中定义中间件文件&#xff0c;如 auth.js&#xff0c;并实现自定义的功能&#xff1b; module.exports (option, app) > {return async function auth(ctx, next) {// 获取配置所传的参数console.log(option);// 实现中间…

Egg 中使用模板引擎及引用静态资源

egg-view-ejs 是 Egg 中比较常用的模板引擎&#xff0c;虽然性能不是很高&#xff0c;但是它的语法规则却是极其的简单&#xff0c;使用起来很方便&#xff0c;下面简单介绍一下它的用法。 1. 安装模板引擎&#xff1b; npm i egg-view-ejs --save 2. 在 config 文件夹下找到…

Egg 中获取 POST 提交的数据

用过Koa的码农都知道&#xff0c;在Koa中获取POST提交的数据需要配置第三方的中间件&#xff0c;而Egg继承于Koa&#xff0c;在这一方面做了优化&#xff0c;获取POST提交的数据不需要再配置其它的中间件了&#xff0c;并添加了安全机制 CSRF 的防范&#xff0c;在Egg中获取用户…

hdu 3477 Temperature

/*原来物理在ACM上也有应用的&#xff0c;有关积分的题目真的是几乎没有做过的一直到比赛的最后才AC的&#xff0c;纠结的说牛顿的冷却定理是参考了baidu的&#xff0c;确切的说不是评自己的水平AC的以后看到非线性的方程要想到积分*/#include <iostream>#include <al…

import torch_geometric.nn报错/lib64/libm.so.6: version `GLIBC_2.27‘ not found

报错信息如下&#xff1a; /lib64/libm.so.6: version GLIBC_2.27 not found (required by /project/***/anaconda3/envs/gypsum/lib/python3.7/site-packages/torch_spline_conv/_basis_cuda.so)原因是 要求GLIBC_2.27,输入&#xff1a;ldd --version但是linux系统只有ldd (G…

申宝解读元宇宙板块依然强势

周三的行情在预期的变盘时间点&#xff0c;产生宽幅剧烈震荡波动&#xff0c;早盘小幅低开以后&#xff0c;诱空一路震荡下跌&#xff0c;下破3469点到3477点&#xff0c;产生背离行情&#xff0c;最低到达3448点&#xff0c;下跌幅度稍微比预期的多一点点&#xff0c;由于在时…

1337: 最大值

1337: 最大值 1.描述 输入一个整数n和n个整数&#xff0c;输出这n个整数的最大值。 输入 输入有两行&#xff1a;第一行是一个正整数n&#xff0c;第二行是n个整数。 输出 输出包含一个整数&#xff0c;即n个数中的最大值&#xff0c;单独占一行。 样例输入 4 3 7 5 6 样例…

无胁科技-TVD每日漏洞情报-2022-11-21

漏洞名称:WordPress plugin tagDiv Composer 授权问题漏洞 漏洞级别:严重 漏洞编号:CVE-2022-3477;CNNVD-202211-2691 相关涉及:WordPress plugin tagDiv Composer 3.5 版本之前 漏洞状态:POC 参考链接:https://tvd.wuthreat.com/#/listDetail?TVD_IDTVD-2022-21962 漏洞名称…

VTK学习之光照和相机

目录 一、VTK光照 1、关于vtkLight常用的方法 2、最终效果 二、相机设置 1、相机设置 2、效果 一、VTK光照 通过设置光照&#xff0c;可以达到不同颜色的目的&#xff0c;参考博客&#xff1a; VTK修炼之道7_三维场景基本要素:光照_vtk 光照_沈子恒的博客-CSDN博客 1…

达梦数据库在不修改SQL的情况下为SQL指定HINT

前言 在Oracle中可以使用outline、SQL PROFILE等手段去在无需修改SQL语句的情况下&#xff0c;来保证SQL执行计划在不同硬件环境下相同&#xff0c;从而保证SQL语句在不同环境的执行效率。那么&#xff0c;在达梦数据库中则可以使用SF_INJECT_HINT系统函数达到类似的效果。 SF…

三元锂SOC-OCV修正

按照以下OCV表制作修正电量&#xff1a; 设计思路&#xff1a; 在5-10&#xff0c;10-15.。。。。。之间认为容量随电压的变化是线性的&#xff0c;在温度-20–10&#xff0c;-10-0&#xff0c;0-10…之间认为容量随温度的变化也是线性的。 //soc 当前SOC //temper…

关于float32与float64

tensorflow默认float32(dtype)&#xff0c;numpy默认float64(np.type)&#xff0c;matlab也是默认double。 如果在特定的编程语言里进行强制转换&#xff0c;最好用他们对应的语句&#xff0c;最好不要强行操作&#xff0c;可能会产生一些问题。对于tensorflow想用float64是真的…

史上最强三千六百道脑筋急转弯(6)

3000—地球上什么地方的出生率最高 答案&#xff1a;产房 3001—小张一直朝北走,走着走着他又没有转身可是却走到了正南方,为什么 答案&#xff1a;他越过北极点在向前走就是南方 3002—为什么现代人越来越言而无信 答案&#xff1a;因为有了电话 3003—一个职业登山运动员什么…

你用过的低代码都装备了这四大引擎吗?

低代码开发是一种通过图形化界面和少量编码来快速构建应用程序的方法。尽管增删改查是低代码开发中常见的基本功能&#xff0c;但仅仅通过这些功能的配置&#xff0c;往往只能实现数据的输入和输出&#xff0c;无法满足实际的业务需求。 增删改查功能主要用于对数据进行操作&a…

美的热水器面板php代码,美的热水器故障代码有哪些?

du845968102 2015-12-08 14:48 美的热水器故障代码 1、E1&#xff1a;点火失败或中途熄火 ①由于火焰检测(反馈电极)感应电流较弱时&#xff0c;判定为燃烧器无火&#xff0c;造成程序中断。此时可检查反馈电极是否处于火焰的高温区&#xff0c;调节反馈电极高度&#xff0c;检…

《信息安全等级保护管理办法》公通字[2007]43号

信息安全等级保护管理办法 《信息安全等级保护管理办法》是为规范信息安全等级保护管理&#xff0c;提高信息安全保障能力和水平&#xff0c;维护国家安全、社会稳定和公共利益&#xff0c;保障和促进信息化建设&#xff0c;根据《中华人民共和国计算机信息系统安全保护条例》…

Java List 怎么赋值给另一个List,用等于号可以吗?

公众号请关注"果酱桑", 一起学习,一起进步! 在Java编程中&#xff0c;List是一种常用的数据结构&#xff0c;它可以用来存储一组元素&#xff0c;而且可以动态地添加、删除和修改元素。但是&#xff0c;在实际应用中&#xff0c;我们经常需要将一个List赋值给另一个…

CENTOS下的命令行参数

写在前面 -和 - - &#xff1a;分别代表的是有一个横线&#xff08;一个破折号&#xff09;和两个横线&#xff08;两个破折号&#xff09;&#xff0c;由于编辑器显示的原因只能加上空格用于区分。 概述 在LINUX SHELL中&#xff0c;我们把 - 或 - - 加上一个字符&#xff…