Codeforces Round #386 (Div. 2) 746F(set的运用)

题目大意

给出一个歌单（有n首歌），每个歌都有愉悦值和时间，你可以选择从第x首歌开始听（也就是选择连续的一段），并且你可以选择w首歌让它的时间减半，限制时间为k，求最大的愉悦值

首先我们需要贪心一下，假如从第x首歌开始听，那么要想获得最大的愉悦值，就必须把那些时间最长的歌进行减半处理。

根据这个，我们就需要利用数据结构来进行维护

考虑使用两个set来维护，S1中保存没有被减半的歌曲，S2中保存减半了的歌曲

首先从x=1开始听，每新加进来一首歌i，进行如下处理

1、S2中还没有w首歌，就直接放进S2里

2、S2中已经有了w首歌，那么就抽出其中时间最短的歌与i比较，如果i的时间大，就把那个最短的歌放到S1中，把i放到S2中；否则就把i放到S1中

假如无法放入歌曲，那么就统计出来当前的愉悦值，然后把第一首歌删掉

删除时要注意，如果删掉的元素在S1中就不需要额外处理，如果在S2中，就要把S1中最长的歌再放到S2中

然后直到最后一首歌被抽出，输出最大的答案

每首歌只会被放入或抽出1次，所以复杂度是nlogn

#include <iostream>

#include <cstdio>

#include <set>

using namespace std;

const int maxn = *;

struct Data

{

    int t, id;

    Data() {}

    Data(int _t, int _id) { t = _t; id = _id; }

    bool operator <(const Data& B) const

    { return (t == B.t) ? (id < B.id) : t < B.t; }

    bool operator == (const Data& B) const

    { return t == B.t && id == B.id; }

};

struct node

{

    int t, v;

}a[maxn];

set<Data> S1, S2;

int nowt = , tot = -, st = ;

void Insert(int ty, int t, int id)

{

    if(ty == )

    {

        S1.insert(Data(t, id));

        nowt += t;

    } else

    {

        S2.insert(Data(t, id));

        nowt += ((t-)/+);

    }

}

void Erase(int ty, int t, int id)

{

    if(ty == )

    {

        S1.erase(Data(t, id));

        nowt -= t;

    } else

    {

        S2.erase(Data(t, id));

        nowt -= ((t-)/+);

    }

}

void ERASE(int st)

{

    if(S1.find(Data(a[st].t, st)) != S1.end()) Erase(, a[st].t, st);

        else

        {

            Erase(, a[st].t, st);

            if(S1.size() > )

            {

                Data tmp = *(--S1.end());

                Erase(, tmp.t, tmp.id);

                Insert(, tmp.t, tmp.id);

            }

        }

}

int n, w, k;

int main()

{

    cin>>n>>w>>k;

    for(int i = ; i < n; i++) cin>>a[i].v;

    for(int i = ; i < n; i++) cin>>a[i].t;

    int ans = , ANS = ;

    while(st != n)

    {

        while(nowt <= k)

        {

            tot++;

            if(tot >= n) break;

            if(S2.size() < w)

            {

                Insert(, a[tot].t, tot);

            }

            else

            {

                Data tmp = *S2.begin();

                if(tmp.t < a[tot].t)

                {

                    Erase(, tmp.t, tmp.id);

                    Insert(, tmp.t, tmp.id);

                    Insert(, a[tot].t, tot);

                } else

                Insert(, a[tot].t, tot);

            }

            if(nowt <= k)  ans += a[tot].v;

            else

            {

                ERASE(tot);

                tot--;

                break;

            }

            ANS = max(ANS, ans);

        }

        ERASE(st);

        ans -= a[st].v;

        st++;

    }

    cout<<ANS<<endl;

}

巴特西

Codeforces Round #386 (Div. 2) 746F(set的运用)

最新文章

热门文章