1554: SG Value （巧妙的模拟题，也属于思维题）

时间：2021-12-23 16:25:04

1554: SG Value

Submit Page    Summary    Time Limit: 5 Sec     Memory Limit: 256 Mb     Submitted: 497     Solved: 167

Description

The SG value of a set (multiset) is the minimum positive integer that could not be constituted of the number in this set.
You will be start with an empty set, now there are two opertions:
1. insert a number x into the set;
2. query the SG value of current set.

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1e5) -- the total number of opertions.
The next N lines contain one opertion each.
1 x means insert a namber x into the set;
2 means query the SG value of current set.

Output

For each query output the SG value of current set.

Sample Input

5

2

1 1

2

1 1

2

Sample Output

1

2

3
题目意思：
两种操作
1 a ：往集合添加一个元素a
2：询问这个集合中任意元素相加不能得到的最小数的值
这道题总是不断地去找当前所能处的最小值能否被当前的最小值加上其前部的一堆可抵达数到达当前位置
也就是 minn < *s.begin() , 说明此时内部最小的元素是不影响这个值的，否则 minn+=*s.begin()，然后剔除最小值，不断往下访问
在这里因为相同数据也可以同时保存在集合内，所以不采用set（会删除重复元素），而是使用multiset。
 
 
#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define max_v 10005

using namespace std;

typedef long long LL;

multiset<int> s;

int main()

{

    int n;

    while(cin>>n)

    {

        s.clear();

        LL minv=;

        for(int i=;i<n;i++)

        {

            int op;

            cin>>op;

            if(op==)

            {

                int v;

                cin>>v;

                s.insert(v);

            }else

            {

                while(!s.empty()&&minv>=*s.begin())

                {

                    minv+=*s.begin();

                    s.erase(s.begin());

                }

                printf("%lld\n",minv);

            }

        }

    }

    return ;

}

/*

题目意思：

两种操作

1 a ：往集合添加一个元素a

2：询问这个集合中任意元素相加不能得到的最小数的值

这道题总是不断地去找当前所能处的最小值能否被当前的最小值加上其前部的一堆可抵达数到达当前位置

也就是 minn < *s.begin() , 说明此时内部最小的元素是不影响这个值的，否则 minn+=*s.begin()，然后剔除最小值，不断往下访问

在这里因为相同数据也可以同时保存在集合内，所以不采用set（会删除重复元素），而是使用multiset。

/*




相关文章