小记:这题我试着打表 将浮点值乘以100存入数组保存下第一次为该值时的序号,在输入一个浮点数时只要使其乘以100然后从数组里读取即可,但是WA了,后来发现应该是四舍五入的原因,个别的值会出现不对。所以我放弃了使用数组。
思路:对于这样的数量级,没什么好说的,就是玩玩而已。我试了下二分,GNUC++交890MS,C++357MS。
代码:
#include <iostream> #include<math.h> #include <stdlib.h> #include <stdio.h> #include <string.h> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define eps 10e-8 const int MAX_ = 310; double f[MAX_]; int d[MAX_+220]; void init(){ f[0] = 0;mst(d,0); for(int i = 1; ; ++i){ f[i] = f[i-1] + 1.0/(i+1); if(f[i] >= 5.20)break; } } int binary(double x){ int left, right; left = 1; right = 276; if(x < f[left])return left; if(x > f[right])return -1; while(left <= right){ int mid = left + (right - left)/2; if(fabs(f[mid] - x) < eps)return mid; if(x > f[mid-1] && x < f[mid])return mid; if(x > f[mid] && x < f[mid+1])return mid+1; if(x < f[mid])right = mid-1; else if(x > f[mid]) left = mid+1; } return -1; } int main(){ //freopen("f:\\out.txt","w",stdout); double n; init(); //cout<<f[275]<<endl; while(cin>>n){ if(n < eps)break; cout<<d[(int)(n*100)]<<" card(s)"<<endl; /*for(int i = 1; i < 277; ++i){ if(n <= f[i]){ cout<<i<<" card(s)"<<endl;break; } }cout<<endl;*/ } return 0; }