Codeforecs H. Subsegments

思路：

刚开始：

利用map来统计长度为k的一段上的数字及其出现次数，不断更新区段位置，减去退出区段的数字的出现次数，加上新出现的数字及其出现次数，每次都从后向前遍历一遍map，如果遇到一个数且出现次数为1，那么他就是当前区段上的最大数（因为map中已排好序），break，当前循环结束。这种方法果然想的太简单，超时

然后：问题出在哪？前面的不断更新和统计都是在log n时间完成的，应该没有问题。如果出现一种情况，在求当前区间最大值的时候，都是出现不止一次的数，就意味着要遍历整个map。

结果：利用set方便求最值，set自身也是一种树形结构，操作在log n内可以完成。因为set的元素不重样，我们只需将map中出现次数为1的数丢进set，每次更新区段时，先看退出的数出现次数是否减少到一，是则丢入set，不是看是不是在set中出现，如果出现就set中erase它，因为它的出现次数不为1，不在比较范围内。先加入元素看出现次数是否唯一，唯一加入set，不唯一看set中是否有，有就删除。再从set中选最大值，即最后一个（set已经排好序），一轮循环结束。

知识点：

set的insert,empty,end(),rend(),rbegin()（反向迭代器，十分方便）

map的[]访问方式

下面是代码：

 #include <iostream>

 #include <map>

 #include <set>

 #include <climits>

 #define max_n 100005

 using namespace std;

 int a[max_n];

 map<int,int> num;

 set<int> sets;

 int n;

 int k;

 int main()

 {

     cin >> n >> k;

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

     {

         cin >> a[i];

     }

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

     {

         num[a[i]]++;

         if(num[a[i]]==)

         {

             sets.insert(a[i]);

         }

         else

         {

             if(sets.find(a[i])!=sets.end())

             {

                 sets.erase(a[i]);

             }

         }

     }

     if(sets.empty())

     {

         cout << "Nothing" << endl;

     }

     else

     {

         auto i = sets.rbegin();

         cout << *i << endl;

     }

     int f = ;

     int b = k;

     for(;b<n;f++,b++)

     {

         num[a[f]]--;

         num[a[b]]++;

         if(num[a[f]]==)

         {

             sets.insert(a[f]);

         }

         else

         {

             if(sets.find(a[f])!=sets.end())

             {

                 sets.erase(a[f]);

             }

         }

         if(num[a[b]]==)

         {

             sets.insert(a[b]);

         }

         else

         {

             if(sets.find(a[b])!=sets.end())

             {

                 sets.erase(a[b]);

             }

         }

         if(sets.empty())

         {

             cout << "Nothing" << endl;

         }

         else

         {

             auto i = sets.rbegin();

             cout << *i << endl;

         }

         /*for(auto i = num.rbegin();i!=num.rend();i++)

         {

             cout << i->first << "-" << i->second << endl;

         }*/

     }

 }

巴特西

Codeforecs H. Subsegments

最新文章

热门文章