UVALive 8519 贪心 + 线段树

发表于 | 分类于 | 阅读次数：

线段树维护区间最小以及查询。

链接

题意

每场比赛有K个题目，题目的难度由数字来表示，而且难度必须是连续的，比如说1 2 3 4 5,然后告诉你每种难度的题目有多少个，现在让你安排最多的比赛场数。

思路

贪心的思路，从第一个难度的题目开始往后看，查询区间内最小值，把答案加上这个最小值，然后再把区间内的数字减去这个值。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 100005;
struct node{
   ll Min;
}tr[maxn << 2];
ll a[maxn],lazy[maxn << 2];
void pushdown(int node)
{
    if(lazy[node] == 0) return;
    lazy[node << 1] += lazy[node];
    lazy[node << 1|1] += lazy[node];
    tr[node << 1].Min +=  lazy[node];
    tr[node << 1|1].Min += lazy[node];
    lazy[node] = 0;
}
void build(int node, int l, int r)
{
    if(l == r)
    {
        tr[node].Min = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1|1, mid + 1, r);
    tr[node].Min = min(tr[node << 1].Min, tr[node << 1|1].Min);
}

void update(int node, int l, int r, int ul, int ur,int value)
{
    if(ul > r || ur < l) return;
    if(ul <= l && ur >= r){
        tr[node].Min += value;
        lazy[node] += value;
        return;
    }
    pushdown(node);
    int mid = (l + r) >> 1;
    update(node << 1, l, mid ,ul, ur, value);
    update(node << 1|1, mid + 1, r, ul, ur, value);
    tr[node].Min = min(tr[node << 1].Min, tr[node << 1|1].Min);
}
ll Min;
void query(int node, int l, int r, int ql, int qr)
{
    if(ql > r || qr < l) return;
    if(ql <= l && qr >= r)
    {
          Min = min(Min,tr[node].Min);
          return;
    }
    int mid = (l + r) >> 1;
    pushdown(node);
    query(node << 1, l, mid , ql, qr);
    query(node << 1|1, mid + 1, r, ql, qr);
}
int main()
{
    int T,n,k;
    cin >> T;
    while(T--)
    {
        memset(lazy, 0, sizeof(lazy));
        scanf("%d %d",&n,&k);
        for(int i = 1;i <= n; ++i)
            scanf("%lld",&a[i]);
        build(1,1,n);
        ll cnt = 0;
        for(int i = 1; i <= n - k + 1; ++i)
        {
            Min = inf;
            query(1,1,n,i, i + k - 1);
            if(Min > 0 && Min != inf)
            {
                cnt += Min;
                update(1,1,n, i, i + k - 1, -Min);
            }
        }
        cout << cnt << '\n';
    }
}