CodeForces 460C (Present)[二分，贪心，线段树]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/460/C

二分一个高度，检查时考虑这样一种贪心策略：扫描数组，如果遇到高度小于二分值的就把它和它后面连续w个数加上a[i]-mid，如果能让所有的数大于mid，则二分值是满足条件的。

这题直接暴力会超时，线段树会卡常数，建树时必须是O(n)的复杂度，我尝试一开始建立一颗线段树并把它保存起来，每次重新建树时直接memcpy，卡过了这道题。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100009;
int n,m,w;
int a[maxn];


const int maxm = 510000;
int sumv[maxm];
int addv[maxm];
int sumvt[maxm];
int addvt[maxm];


void maintain(int o, int L, int R) {
    int lc=o*2, rc=o*2+1;
    sumv[o]=0;
    if(R>L) {
        sumv[o]=sumv[lc]+sumv[rc];
    }
    sumv[o]+=addv[o]*(R-L+1);
}
int v;
int y1,y2;
void update(int o, int L, int R) {
    int lc=o*2,rc=o*2+1;
    if(y1<=L && y2>=R) {
        addv[o]+=v;
    }
    else {
        int M=L+(R-L)/2;
        if(y1<=M) update(lc,L,M);
        if(y2>M) update(rc,M+1,R);
    }
    maintain(o,L,R);
}
int _sum;
void query(int o,int L, int R, int add) {
    if(y1<=L && y2>=R) {
        _sum+=sumv[o]+add*(R-L+1);
    }
    else {
        int M=L+(R-L)/2;
        if(y1<=M) query(o*2,L,M,add+addv[o]);
        if(y2>M) query(o*2+1,M+1,R,add+addv[o]);
    }
}



bool check(int mid) {
    memcpy(sumv,sumvt,sizeof(sumvt));
    memcpy(addv,addvt,sizeof(addvt));
    int left = m;
    int i=1;
    int d,now;
    while(left>=0 && i<=n) {
        _sum=0;
        y1=y2=i;
        query(1,1,n,0);
        now=_sum;
        if(now<mid) {
            d=mid-now;
            left-=d;
            if(left<0) break;
            y1=i,y2=min(n,i+w-1);
            v=d;
            update(1,1,n);
        }
        i++;
    }
    if(left < 0) return 0;
    else return 1;
}
int main() {
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    memset(sumv,0,sizeof(sumv));
    memset(addv,0,sizeof(addv));
    for(int i=1;i<=n;i++) {
        y1=y2=i;
        v=a[i];
        update(1,1,n);
    }
    memcpy(sumvt,sumv,sizeof(sumv));
    memcpy(addvt,addv,sizeof(addv));
    int l=0,r=1001000000,mid;
    while(l<r) {
        mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",l);
}