【NOIP2016提高A组模拟9.9】运输妹子

2024-05-29 03:18

本文主要是介绍【NOIP2016提高A组模拟9.9】运输妹子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

小轩轩是一位非同一般的的大农(lao)场(si)主(ji),他有一大片非同一般的农田,并且坐落在一条公路旁(可以认为是数轴),在他的农田里种的东西也非同一般——不是什么水稻小麦,而是妹子。
在小轩轩的细心培育下,他的大片农田都要结出妹子啦!但是他的农田分布实在是太广阔了,他担心自己的妹子会令路过的人想入非非,于是他想要把所有农田上的妹子都集中到一个仓库里面,贮存起来。可是妹子太多,他叫来了一辆卡车,这辆卡车刚好可以装满一个农田的妹子,并且在满载的情况下,运满满一卡车妹子走1米的费用是1元。由于小轩轩技术精湛,他的每个农田产量都是一样的。即把一个农田的妹子都运到仓库费用为农田与仓库坐标差值的绝对值。理想很美好,但现实很残酷——小轩轩还没有想好在什么位置搭建他的仓库,而且他的运输费用是有限的。
请你帮忙计算一下,在什么位置搭建仓库,使得小轩轩能收获的妹子最多。(仓库的位置可与农田的位置重合,并且在公路长度范围内)。

Input

第一行三个正整数 N,L,W,分别表示农田个数、公路总长度、总钱数。
接下来 N 行,每一行描述一个农田的坐标。(可能有多个农田位于同一位置)

Output

一个整数,小轩轩最多能够收藏多少个农田的妹子。

Sample Input

5 23 18
4
6
14
18
22

Sample Output

3

Data Constraint

对于 30% 的数据,N≤1000,L≤10000。
对于 60% 的数据,N≤10000,L≤1000000。
对于 100% 的数据,N≤100000,L≤1000000000,W≤2000000000000000

Solution

看到数据范围,会发现基于L和W的算法是不行的。
然后提出两个猜想,仓库肯定建在农田上,而且必定是一段农田的第中位数个农田
于是二分答案,枚举中间的建仓库的那个农田,O(1)求出在当前情况下需要多少费用,判断即可
如何O(1)求呢?预处理一下就行了,自己YY
时间复杂度 O(nlog2n)

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 101000
#define ll long long
using namespace std;
int n;
ll m,w,a[N],b[N],c[N];
int main()
{scanf("%d %lld %lld",&n,&m,&w);fo(i,1,n) scanf("%lld",&a[i]);a[n+1]=m;sort(a+1,a+n+2);fo(i,1,n) b[i]=b[i-1]+i*(a[i]-a[i-1]);fd(i,n,1) c[i]=c[i+1]+(n-i+1)*(a[i+1]-a[i]);ll l=1,r=n;while(l+1<r){int mm=(l+r)/2;ll jy=9223372036854775807ll;fo(i,mm/2-3,n-mm/2+3){int z1=i-((mm-1)/2),z2=i+mm-1-((mm-1)/2);if(z1<1||z2>n) continue;ll jy1=b[i]-b[z1]-z1*(a[i]-a[z1]);ll jy2=c[i]-c[z2]-(n-z2+1)*(a[z2]-a[i]);jy=min(jy,jy1+jy2);}if(jy<=w)l=mm;else r=mm;}ll jy=9223372036854775807ll;fo(i,1,n){int z1=i-((r-1)/2),z2=i+r-1-((r-1)/2);if(z1<1||z2>n) continue;ll jy1=b[i]-b[z1]-z1*(a[i]-a[z1]);ll jy2=c[i]-c[z2]-(n-z2+1)*(a[z2]-a[i]);jy=min(jy,jy1+jy2);}if(jy<=w) l=r;printf("%lld",l);
}

这篇关于【NOIP2016提高A组模拟9.9】运输妹子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012489

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

GIS图形库更新2024.8.4-9.9

更多精彩内容请访问 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信:digital_twin123 Cesium 本期发布了1.121 版本。重大新闻,Cesium被Bentley收购。 ✨ 功能和改进 默认启用 MSAA,采样 4 次。若要关闭 MSAA,则可以设置scene.msaaSamples = 1。但是通过比较,发现并没有多大改善。

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+