2600: [Ioi2011]ricehubh

Description

乡间有一条笔直而长的路称为“米道”。沿着这条米道上 R 块稻田，每块稻田的坐标均
为一个 1 到 L 之间(含 1 和 L)的整数。这些稻田按照坐标以不减的顺序给出，即对于 0 ≤ i <
R，稻田 i 的坐标 X[i]满足 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。
注意：可能有多块稻田位于同一个坐标上。
我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样，米仓将建在米道上，其
坐标也是一个 1 到 L 之间的整数（含 1 和 L）。这个米仓可以建在满足上述条件的任一个位
置上，包括那些原来已有一个或多个稻田存在的位置。
在收获季节，每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓，需要雇
用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 1 元。換言之，
将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。
不幸的是，今年预算有限，我们至多只能花费 B 元运费。你的任务是要帮我们找出一个
建造米仓的位置，可以收集到尽可能多的稻米。

Input

第一行三个整数 R L B
接下来R行每行一个整数表示X[i]

Output

一个整数最多稻米数

Sample Input

5 20 6
1
2
10
12
14

Sample Output

3
HINT
1 ≤ R ≤ 100,000
1 ≤ L ≤ 1,000,000,000
0 ≤ B ≤ 2,000,000,000,000,000

解析：其实去画一画或想一下就会发现，米仓在两个稻田间的任意位置，两个稻田的运费之和都相等，那么我们不如直接考虑将它建在哪一块稻田上。

二分枚举稻田数x，然后用一个for循环来枚举我们所假想收割的x个稻田中最左边的那个稻田位置为l,然后通过x推出r,mi（最右边的位置和中间位置）。谷仓在中间时为最优解（这个自己去试试画出来想）所以谷仓位置为mi。好啦那么我们枚举的这段区间的费用是多少呢？可能很多人会和我一样第一反应是用一个for循环来计算，可是之前的枚举已经是O(nlogn)了，这就决定了我们的计算最好复杂度为O（1）。我们用前缀和来实现。首先设费用为sum,f为一个数组，这个数组中f[i]储存的是1~i块稻田的坐标和，a数组用来储存每块稻田的坐标，设一个变量now来表示米仓的坐标（就是a[now]），则公式为：

sum=now*(mi-l)-(f[mi-1]-f[l-1])+(f[r]-f[mi])-now*(r-mi);

为什么这么做呢，下面来解释一下。

我们需要把区间分成左右两边来做，左边的费用等于=now-a[l]+now-a[l+1]+now-a[l+2]+....+now-a[mi-1];我们可以发现他是有多个now-a[?]组合而成，有几项呢？不拿算出总共有mi-l(不是数字1是L！）项，则式子变为=now*(mi-l)-(a[l]+a[l+1]+a[l+2]+....+a[mi-1]);好啦那么a[l]+..+a[mi-1]即为第l块稻田到第mi-1块稻田的坐标之和，完全可以用前缀和直接表示成f[mi-1]-f[l-1],好啦左边的式子最终成为：now*(mi-l)-(f[mi-1]-f[l-1])，同理右边的式子也可以这样推出来（不写啦）。

算出sum后只要比B元小，就成立了，否则不成立。

程序：

#include<iostream>

#include<cstdio>

using namespace std;

long long f[],now,k,ans,a[],sum,n,l,b,lef,righ,mid;

bool check(long long x)

{

  int i,l,r,mi;

  for (i=;i<=n-x+;++i)

  {

      l=i;（最左边的稻田） r=i+x-（最右边的稻田）; mi=(l+r)/（米仓）;

      now=a[mi];（米仓坐标）

      sum=now*(mi-l)-(f[mi-]-f[l-])+(f[r]-f[mi])-now*(r-mi);

（式子的具体推法已经写在上面了）

      if (sum<=b) return true;

  }

  return false;

}

int main()

{

  cin>>n>>l>>b;

 for (int i=;i<=n;++i) cin>>a[i];

 f[]=;

 for (int i=;i<=n;++i) f[i]=f[i-]+a[i];（前i个稻田的坐标之和）

 lef=;

 righ=n+;

 ans=;

 while (lef<=righ) （枚举有几块稻田能收割）

 {

     mid=(lef+righ)/;

     if (check(mid)==true)

     {

      lef=mid+;

      if (ans<mid) ans=mid;

     }

        else righ=mid-;

  }

  cout<<ans<<endl;

  return ;

}

好啦好啦。

秒客网