【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

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);
}

秒客网