問題
http://community.topcoder.com/stat?c=problem_statement&pm=3561&rd=6519
ソートアルゴリズムの計算量を計算したい。
計算量はc*n*log2(n)で表わされ、これをtime以下でかつ最大となるときのｎを求めたい。
cとtimeはあらかじめ与えられる。
解き方
nが一意に決まれば計算量は算出できるので、二分探索が適用できる。
コード
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SortEstimate {
public: double howMany(int c, int time) {
double low=0.0,high=1e+18;
FORE(i,0,100){
double mid=(low+high)/2.0;
if(c*mid*log(mid)/log(2)<=time)low=mid;
else high=mid;
}
return low;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SortEstimate {
public: double howMany(int c, int time) {
double low=0.0,high=1e+18;
FORE(i,0,100){
double mid=(low+high)/2.0;
if(c*mid*log(mid)/log(2)<=time)low=mid;
else high=mid;
}
return low;
}
};