hdu 1031 (partial sort problem, nth_element, stable_partition, lambda expression) 分类: hdoj 2015-06-15 17:47 26人阅读 评论(0) 收藏

partial sort.

first use std::nth_element to find pivot,

then use std::stable_partition with the pivot to partition the largest k, whose indices are in acsending order, print them in reverse order.

p.s. lambda expression is also used.

STL is powerful.

#include <cstdio>
#include <vector>
#include <algorithm> struct IRPair{
int ind;
double rate;
}; int main() {
//freopen("input.txt","r",stdin);
int num_people, num_candidate, num_final, i,j;
double tmp;
std::vector<IRPair> vec;
std::vector<double> ratings;
while(scanf("%d%d%d",&num_people,&num_candidate,&num_final)!=EOF) {
vec.resize(num_candidate);
ratings.clear(); ratings.resize(num_candidate);
for(i=0;i<num_people;++i)
for(j=0;j<num_candidate;++j) { scanf("%lf",&tmp); ratings[j]+=tmp; }
for(i=0;i<num_candidate;++i) { vec[i].ind=i+1; vec[i].rate=ratings[i]; }
std::nth_element(&ratings[0],&ratings[num_candidate-num_final],&ratings[num_candidate]);
tmp=ratings[num_candidate-num_final];
std::stable_partition(&vec[0],&vec[num_candidate],[tmp](const IRPair &x) { return x.rate>=tmp; });
for(i=num_final-1;i>0;--i) { printf("%d ",vec[i].ind);}
printf("%d\n",vec[0].ind);
}
return 0;
}

156 ms for double, vector

140 ms for float, vector

140 ms for double, array

124 ms for float, arry

time for array / time for vector = 90%

版权声明:本文为博主原创文章,未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.

上一篇:循序渐进Python3(八) -- 0 -- 初识socket


下一篇:Django中的auth模块