Algoogle

Algorithm for Programming Contest

PKU 2018 Best Cow Fences

Category: PKU Tag: binary-search

Best Cow Fences

問題概要


数列が与えられる. 長さF以上の連続した数字を取ってきてその平均の最大値を求めよ.

解法


平均の最大化といえば二分探索.
入力の数列をA, 平均値をx, 連続する区間を[j,k)とすると
{$ math $} x=\frac{\sum_{i=j}^{k-1}A_i}{k-j} {$ endmath $}
{$ math $} \sum_{i=j}^{k-1}A_i - (k-j)x = 0 {$ endmath $}
よってあるx以上の解が存在するかは
{$ math $} \sum_{i=j}^{k-1}A_i - (k-j)x \geq 0 {$ endmath $}
を満たす区間[j,k)が存在するかで判定すれば良い.
連続部分和の最大を求めるのはO(N)程度でできることはよく知られている(この場合は0以上のものがみつかればそこで終了).
{$ math $} M_i = max{sum(0,j) | i \leq j < N} {$ endmath $}
とすると(M_iは大きい方から決めていけばO(N)で求まる),
区間の開始をiとして幅F以上とった時の最大値は
{$ math $} M_{i+F} - sum(0,i) {$ endmath $}
とわかる. このiを全て試せば良い.

コード


(2018.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <cstdio>

using namespace std;

#define int long long

const int inf = (int)1e18;
int N, F;
int field[100010];
int sum[100010];
int M[300010];

bool can(int x){
    sum[0] = 0; M[N+1] = -inf;
    for(int i = 0; i < N; i++){
        sum[i+1] = sum[i] + field[i] - x;
        M[i*2+1] = -inf;
        M[i*2] = -inf;
    }
    for(int i = N; i >= 0; i--)
        M[i] = max(M[i+1], sum[i]);

    for(int i = 0; i < N; i++)
        if(M[i+F]-sum[i] >= 0) return 1;
    return 0;
}

signed main(){
    scanf("%lld%lld", &N, &F);
    for(int i = 0; i < N; i++){
        scanf("%lld", field+i);
        field[i] *= 1000;
    }
    int lb = 0, ub = 1000*2000+1000;
    while(ub - lb > 1){
        int mid = (lb + ub) / 2;
        if(can(mid)) lb = mid;
        else ub = mid;
    }
    printf("%lld\n", lb);
    return 0;
}

Comments