UVA 8519 - Arrangement for Contests

发表于 更新于 分类于 本文字数： 3.8k 阅读时长 ≈ 3 分钟

题目描述

As a sponsor of programming contests, Yu has many factors to consider. Recently, he has found that the difficulties of problems can be a serious factor.
For novices, they may simply ignore the problems that are too hard; and for experts in programming contests, an easy problem almost means nothing. Moreover, if a contest consists of both easy and hard questions, it will not satisfy them — but make them unhappy for both reasons.
Therefore, Yu has come up with an idea: holding different kinds of contests! Novices tend to participant in a contest is known as an easy one, but will not join a hard one.
In details, suppose the difficulty of a problem can be measured as a positive integer, $i$. The bigger number means that the problem is harder. In Yu’s design, a contest consists of several problems with consistent difficulties. Formally, if a contest has k problem, then their difficulties must be $i, i + 1, . . . , i + k − 1$. This is because if there are two problems with same difficulties, their functions in the contest will be the same, which is not good; and if two problems have a big gap in difficulties, there will be questions that are mentioned above. Now, a contest with difficulty $1,2,3,4,5$ is obviously a simple one, and a contest with $5,6,7,8,9$ can be a hard one.
Yu has a large amount of problems, and he measures all the difficulties. Now, he wants to hold as many contests as possible. Do you know how many contests can he hold?

输入描述

In the first line there is an integer $T (1 ≤ T ≤ 10)$, showing that there are T test cases. Each test case
consists of two lines.
For each test case, in the first line are two integers $N, K (1 ≤ K ≤ N ≤ 100, 000)$, where $N$ means
the kinds of difficulties, and $K$ is the number of questions that a contest may have.
In the second line, there are $N$ numbers $a[i] (0 ≤ a[i] ≤ 10^9)$, the $i_{th}$ indicates the number of
questions with difficulty $i$.

输出描述

For each test case, the output should be an integer, indicating the maximum number of contests that
Yu can hold.

样例输入

1
2
3
4
5
6
7
3
3 2
1 2 1
6 3
1 5 3 4 7 6
9 4
2 7 1 3 6 5 8 9 4

样例输出

1
2
3
2
5
6

思路

最初将$index$设为$1$，然后将$[index, index+k-1]$区间所有值减去改区间的最小值，将$index$设为该区间最小值的下标$+1$。

由于涉及区间修改和区间查询，考虑采用线段树来维护。区间查询不只需要得到区间的最小值，也要得到该最小值对应的下标，所以需要对求极值的线段树进行改进。

考虑到 pair 类型可以带着两个值返回，它的大小比较是先比较 first，所以将区间极值作为 first，下标作为 second，方便了线段树内部的比较。

代码

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
#include<bits/stdc++.h>
using namespace std;

struct nod{
    long long l,r,lazy;
    pair<long long,long long> mins;
}t[400002];
long long n,k,a[100002];
void buildtree(long long l,long long r,long long root)
{
    t[root].l=l;t[root].r=r;
    long long x=(t[root].l+t[root].r)/2,ch=root*2;
    if(t[root].l==t[root].r)
    {
        t[root].mins=make_pair(a[l],l);
        return;
    }
    buildtree(l,x,ch);
    buildtree(x+1,r,ch+1);
    t[root].mins=min(t[ch].mins,t[ch+1].mins);
    t[root].lazy=0;
    return;
}
void changes(long long l,long long r,long long root,long long num)
{
    long long x=(t[root].l+t[root].r)/2,ch=root*2;
    if(t[root].l==l && t[root].r==r)
    {
        t[root].lazy+=num;
        return;
    }
    if(r<=x)changes(l,r,ch,num);
    if(l>x)changes(l,r,ch+1,num);
    if(l<=x && r>x)
    {
        changes(l,x,ch,num);
        changes(x+1,r,ch+1,num);
    }
    t[root].mins.first+=num;
}
pair<long long,long long> finds(long long l,long long r,long long root)
{
    long long x=(t[root].l+t[root].r)/2,ch=root*2;
    if(t[root].lazy)
    {
        t[root].mins.first+=t[root].lazy;
        if(t[root].l!=t[root].r)
        {
            t[ch].lazy+=t[root].lazy;
            t[ch+1].lazy+=t[root].lazy;
        }
        t[root].lazy=0;
    }
    if(t[root].l==l && t[root].r==r)return t[root].mins;
    if(r<=x)return finds(l,r,ch);
    if(l>x)return finds(l,r,ch+1);
    return min(finds(l,x,ch),finds(x+1,r,ch+1));
}
int main(){
    pair<long long,long long> mins;
    int tt;
    scanf("%d",&tt);
    while(tt--){
        long long ans=0;
        scanf("%lld%lld",&n,&k);
        for(long long i=1;i<=n;++i){
            scanf("%lld",&a[i]);
        }
        buildtree(1,n,1);
        long long index=1;
        while(index<=n-k+1){
            mins=finds(index,index+k-1,1);
            ans+=mins.first;
            changes(index,index+k-1,1,-mins.first);
            index=mins.second+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}