UVALive 6915 Leveling Ground 优先队列+map来维护区间最值

UESTC 2016 Summer Training #19

UVALive 6915

My Solution

//!!!!!!  这个UVALive 的题， 由于少了最后一个换行/*if(T) printf("n") 或者说 if(kase < T) printf("n") */， WA了不知道多少发⊙﹏⊙‖∣， 然后把那句代码去掉然后过了，太坑了

把那些花费都 *2, 最后在ans/2.0

类似于Two Pointers的思想

维护区间的sum， 然后移动的时候加上右边多出的一个， 减点左边少掉的那个

然后用优先队列维护区间最值

 priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >lowest;

这个是按照 first 键值的小根堆

所以对应每个在访问的区间， 判断lowest.top()是否在区间内， 如果不在区间内就pop()掉， 直到找到那个在区间内的最小值

复杂度 O(n)

training 的Contest的时候这个题目是队友来代码实现的， 所以向队友nardo 要了代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int T;
long long ht[1000100];

int main(){
    cin >> T;
    for(int kase = 1;kase <= T;++kase){ long long ans = 0; long long N,M; char s[1000100]; cin >> N >> M;
        scanf("%s",s+1);
        memset(ht,0,sizeof ht);
        ht[0] = 2100000;
        s[0] = '_';
        for(ll i = 1;i <= N;++i){
            if(s[i] == '/' && s[i-1] == '_') ht[i] = ht[i-1] + 1;
            if(s[i] == '/' && s[i-1] == '/') ht[i] = ht[i-1] + 2;
            if(s[i] == '/' && s[i-1] == '\')ht[i] = ht[i-1];
            if(s[i] == '\'&& s[i-1] == '_') ht[i] = ht[i-1] - 1;
            if(s[i] == '\'&& s[i-1] == '\')ht[i] = ht[i-1] - 2;
            if(s[i] == '\'&& s[i-1] == '/') ht[i] = ht[i-1];
            if(s[i] == '_' && s[i-1] == '_') ht[i] = ht[i-1];
            if(s[i] == '_' && s[i-1] == '/') ht[i] = ht[i-1] + 1;
            if(s[i] == '_' && s[i-1] == '\')ht[i] = ht[i-1] - 1;
        }
        long long sum = 0;
        priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >lowest;
        for(ll i = 1;i <= M;++i){
            sum += ht[i];
            lowest.push(make_pair(ht[i] / 2 * 2,i));
        }
        ans = sum - lowest.top().first * M;

        for(ll i = M + 1;i <= N;++i){
            sum -= ht[i - M];
            sum += ht[i];
            lowest.push(make_pair(ht[i] / 2 * 2,i));
            while(lowest.top().second <= i - M) lowest.pop();
            ans = min(ans,sum - lowest.top().first * M);
        }

        printf("Case #%d: %.1fn",kase,ans/2.0);
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx