SPOJ ADAFIELD Ada and Field（STL的使用：set，multiset，map的迭代器）题解

题意：n*m的方格，“0 x”表示x轴在x位置切一刀，“0 y”表示y轴在y位置切一刀，每次操作后输出当前面积最大矩形。

思路：用set分别储存x轴y轴分割的点，用multiset（可重复）储存x轴y轴边，每次输出最大的长和最大的宽的积。题目可能重复切。multiset如果直接erase(13)会把所有的13都删掉，如果只想删一个则erase(multiset.find(13))。第一次知道set自带二分...

这里multiset也可以用map<int, int, greater<int> >，然后用迭代器指向最后一个key就行了

代码：

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn =  + ;

const int seed = ;

const int MOD =  + ;

const int INF = 0x3f3f3f3f;

set<ll> x, y;

multiset<ll> lenx, leny;

int main(){

    int T;

    ll n, m, q;

    scanf("%d", &T);

    while(T--){

        scanf("%lld%lld%lld", &n, &m, &q);

        x.clear();

        y.clear();

        lenx.clear();

        leny.clear();

        x.insert(),x.insert(n),lenx.insert(n);

        y.insert(),y.insert(m),leny.insert(m);

        set<ll>::iterator it;

        while(q--){

            ll o, p;

            scanf("%lld%lld", &o, &p);

            if(o ==  && x.count(p) == ){

                it = x.lower_bound(p);

                lenx.insert(*it - p);

                int len = *it - *(--it);

                lenx.erase(lenx.find(len));

                lenx.insert(p - *it);

                x.insert(p);

            }

            else if(o ==  && y.count(p) == ){

                it = y.lower_bound(p);

                leny.insert(*it - p);

                int len = *it - *(--it);

                leny.erase(leny.find(len));

                leny.insert(p - *it);

                y.insert(p);

            }

            it = lenx.end();

            ll chang = *(--it);

            it = leny.end();

            ll kuan = *(--it);

            printf("%lld\n", chang * kuan);

        }

    }

    return ;

}

巴特西

SPOJ ADAFIELD Ada and Field（STL的使用：set，multiset，map的迭代器）题解

最新文章

热门文章