对于需排序的题而言,使用map这种 模板 好吗?

P1093 [NOIP2007 普及组] 奖学金

肥婆纳妾 @ 2018-08-27 12:50:53

感觉结构体 + 排序 都可以使用 map来实现,不知道 map的效率 如何,值不值得 当作刷题的 模板 解决问题呢?
以下是关于这道题,我通过的 代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,score[3],count=0;
    map<int,map<int,vector<int>>>data;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>score[0]>>score[1]>>score[2];
        data[accumulate(score,score+3,0)][score[0]].push_back(i);
    }
    for(auto ritor=data.rbegin();ritor!=data.rend();++ritor){
        for(auto ritor_1=ritor->second.rbegin();ritor_1!=ritor->second.rend();++ritor_1){
            sort(ritor_1->second.begin(),ritor_1->second.end());
            for(int i=0;i<ritor_1->second.size();++i){
                cout<<ritor_1->second[i]<<" "<<ritor->first<<endl;
                if(++count==5)
                    return 0;
            }
        }
    }
}

by ROY1994 @ 2018-08-27 12:57:05

map常数大


by Little_Ming @ 2018-08-27 12:58:48

@肥婆纳妾 复杂度没错,但Map的常数巨大(里头是平衡树)

其实sort也可以排结构体的


by CHHC @ 2018-08-27 13:06:23

sort的第三个参数了解一下


by Zenurik @ 2018-08-27 13:44:48

手写个cmp就好了啊,用map反而使问题复杂化


|