首页 > 代码库 > HDU 4585 Shaolin (set的应用)

HDU 4585 Shaolin (set的应用)

2024-08-15 17:35:06   214人阅读

　　set是STL中非常方便的工具，可以实现自动去重和排序，可我一直忽视它的重要性，导致吃了好几次亏。

　　在思考这道题的时候，我一直往二分上靠拢，可是二分需要直接插入排序，直接插入排序覆盖的时候复杂度最大是n，肯定不行，所以又想链表，结果链表又没办法二分，着实让我相当矛盾。

　　最后才发现自己忘了这么一个现成的好宝贝，set中有一个lower_bound(num)函数，可以返回第一个大于等于num的数，自动排序，自动二分，一切实现自动化……时间跑了700ms，作为stl的东西也不错，网上博主对stl中map和set的评价也非常高，据说是用了一种平衡红黑树的方法，提升了他们的效率。

　　ps：这个题只用map也可以。

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<map>#include<set>#include<algorithm>using namespace std;#define N 100005map<int,int> id;set<int> st;set<int>::iterator it;void Get_it(int num){    it = st.lower_bound(num);    if(it == st.end())    {        it--;        return;    }    if(it != st.begin())    {        int tmp = *it;        it--;        if(num-*it > tmp-num)        {            it++;        }    }}int main(){//    freopen("A.in.cpp","r",stdin);    int n,ans,k,g,m1 = 1000000000;    while(cin>>n)    {        if(n == 0) break;        st.clear();        st.insert(m1);        id.clear();        id[m1] = 1;        for(int i = 0; i < n; i++)        {            cin>>k>>g;            Get_it(g);            cout<<k<<" "<<id[*it]<<endl;            st.insert(g);            id[g] = k;        }    }    return 0;}

 

HDU 4585 Shaolin (set的应用)


联系
我们