| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
秒过~~~~晒代码~~~~本人第一次一次AC啊~~~~泪奔
用了二分搜索法,设了一些哨兵,为了提高速度。
代码如下:
#include<stdio.h>
#include<string.h>
double result[277];
int flag[7];
void init(void);
main()
{
char word[100000][4];
unsigned long int total;
unsigned long int i=0;
double wordNum;
int pos;
int high,low,mid;
init();
while(1)
{
scanf("%s",word[i]);
if(strcmp(word[i],"0.00") == 0)
break;
i++;
}
total = i;
for(i=0;i<total;i++)
{
wordNum = (word[i][0] - '0') * 1.0 + (word[i][2] - '0') * 0.1 + (word[i][3] - '0') * 0.01;
pos = (int)wordNum;
if(result[flag[pos]] < wordNum)
{
low = flag[pos];
high = flag[pos+1];
}
else
{
low = flag[pos-1];
high = flag[pos];
}
while(1)
{
if((high == (low + 1)) && result[low] < wordNum && result[high] >= wordNum)
{
printf("%d card(s)\n",high);
break;
}
mid = (high + low)/2;
if(result[mid] < wordNum)
low = mid;
else
high = mid;
}
}
}
void init()
{
int i=0;
double sum = 0;
int initFlag = 1;
flag[0] = 0;
result[0] = 0.0;
while(sum <= 5.20)
{
i++;
sum += 1.0/(i+1);
result[i] = sum;
if(sum >= initFlag)
{
flag[initFlag] = i;
initFlag++;
}
}
flag[6] = 276;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator