bzoj 2600 [Ioi2011] ricehub 例题

bzoj 2600 [Ioi2011] ricehub 题解

【原题】

2600: [Ioi2011]ricehub

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 298 Solved: 159
[Submit][Status]

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

【分析】据说这是IOI最简单的一道题了，我等蒟蒻仍然抓耳挠腮。神犇们都不屑写题解了，我就来废话几把。

数据范围告诉我们，只能从N（原题中的R）入手。首先我们发现，如果我们确定在L到R的范围内选定谷仓（L和R是稻田下标），那么我们一定可以把谷仓建在下标为(L+R)/2的稻田上。（这是中位数嘛！）而且如果枚举L的话，R肯定是单调递增的。于是单调队列就出现了。

最麻烦的一步就是判断是否要增大R。我用前缀和搞来搞去就好了。（纸上乱推）

【代码】

#include<cstdio>
#define N 100005
using namespace std;
long long n,l,m,i,L,R,mid,ans,sum[N],a[N];
inline long long count(long long R)
{
  mid=(L+R)>>1;
  long long temp1=(sum[R]-sum[mid])-a[mid]*(R-mid);
  long long temp2=a[mid]*(mid-L)-(sum[mid-1]-sum[L-1]);
  return temp1+temp2;
}
int main()
{
  scanf("%lld%lld%lld",&n,&l,&m);
  for (i=1;i<=n;i++)
    scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
  R=1;
  for (L=1;L<=n;L++)
  {
    while (R<n&&count(R+1)<=m) R++;
    if (R-L+1>ans) ans=R-L+1;
  }
  printf("%lld",ans);
  return 0;
}