[STL][降维] UVa 11020 Efficient Solutions

收获:

1 我以前一直疑惑set能不能边遍历边erase,现在看来是可以的,erase(it++)就可以

2 二维转一维的思想,经常使用。

//#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=40000+50;
const int mod=1e9+7;

multiset > S;
multiset >::iterator it;

int main()
{
    int t,cs=0,n,a,b;
    scanf("%d",&t);
    pair p;
    while(t--)
    {
        S.clear();
        cs++;
        if(cs>1)
            puts("");//presentation error
        scanf("%d",&n);
        printf("Case #%d:\n",cs);
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&p.first,&p.second);
            b=p.second;
            if(!S.empty())
            {
                it=S.lower_bound(p);
                if(it==S.begin()||(--it)->second>b)
                {
                    S.insert(p);
                    it=S.upper_bound(p);
                    while(it!=S.end()&&it->second>=b)S.erase(it++);//++ and erase
                }
                printf("%d\n",S.size());
            }
            else
            {
                S.insert(p);
                printf("1\n");
            }
        }
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据