【NOIP2016提高A组模拟9.9】运输妹子
2024-09-05 17:02:26
题目
小轩轩是一位非同一般的的大农(lao)场(si)主(ji),他有一大片非同一般的农田,并且坐落在一条公路旁(可以认为是数轴),在他的农田里种的东西也非同一般——不是什么水稻小麦,而是妹子。
在小轩轩的细心培育下,他的大片农田都要结出妹子啦!但是他的农田分布实在是太广阔了,他担心自己的妹子会令路过的人想入非非,于是他想要把所有农田上的妹子都集中到一个仓库里面,贮存起来。可是妹子太多,他叫来了一辆卡车,这辆卡车刚好可以装满一个农田的妹子,并且在满载的情况下,运满满一卡车妹子走1米的费用是1元。由于小轩轩技术精湛,他的每个农田产量都是一样的。即把一个农田的妹子都运到仓库费用为农田与仓库坐标差值的绝对值。理想很美好,但现实很残酷——小轩轩还没有想好在什么位置搭建他的仓库,而且他的运输费用是有限的。
请你帮忙计算一下,在什么位置搭建仓库,使得小轩轩能收获的妹子最多。(仓库的位置可与农田的位置重合,并且在公路长度范围内)。
分析
易得对于连续的x个农田,
最小的花费一定是最中间的点。
然后二分ans,
在数轴上枚举含ans个点的区间。
随便水水就可以了。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
const int mo=1000000007;
const int N=100005;
using namespace std;
long long a[N],sum[N],n,m,w;
bool ok(int x)
{
long long ans=2147483647,k;
ans*=1000000;
for(int i=1;i<=n-x+1;i++)
{
int l=i,r=i+x-1;
k=0;
int mid=(r+l)/2;
if(x%2)
{
k=sum[r]-sum[mid-1]*2+sum[l-1]-a[mid];
}
else
{
k=sum[r]-sum[mid]*2+sum[l-1];
}
if(k<ans)
ans=k;
}
if(ans<=w)
return true;
else
return false;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&w);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) sum[i]=a[i]+sum[i-1];
int l=0,r=n;
while(l<r-1)
{
int mid=(l+r)/2;
if(ok(mid)) l=mid;
else r=mid-1;
}
if(ok(r))
printf("%d",r);
else
printf("%d",l);
}
最新文章
- 在windows上如何安装python web引擎jinja2
- Python框架之Tornado(一)
- os 模块
- SQL Server 2014云特性:无缝集成公有云
- 手动测试——MTM
- 为mysql在表的某一位置增加一列
- Android 高仿豌豆荚 一键安装app 功能 实现
- poj1947Rebuilding Roads(树形DP)
- js 实现 aop
- 本文实例汇总了C#中@的用法,对C#程序设计来说有不错的借鉴价值。
- Channel Allocation(DFS)
- docker-compose 所带来的方便
- 007.Adding a view to an ASP.NET Core MVC app -- 【在asp.net core mvc中添加视图】
- Linux内核的整体架构简介
- js里面的判断最好做到完全控制
- 在Hadoop集群上的HBase配置
- DTCMS部署错误
- Delphi 创建一个url网址快捷方式代码
- MapReduce -- 好友推荐
- webpack工具、Vue、react模块化
热门文章
- java:HTML(table表格,ul列表)和CSS(导入.css文件,三种定义颜色方式,三种样式选择器,a标签属性顺序,)
- 使用putty远程登录Ubuntu时,报Network error:Connection refused错误及解决(记录)
- mysql——多表——外连接查询——左连接、右连接、复合条件查询
- JSR303 校验扩展(分组、按顺序校验)
- vue中Runtime-Compiler和Runtime-only的区别
- java方法形参是引用类型
- IDEA怎么关闭暂时不用的工程
- ds replicas是什么
- zuul开发实战(限流,超时解决)
- 生成二维码功能(js前端)