首页 > 代码库 > ACM-二分搜索之Can you solve this equation?——hdu2199

ACM-二分搜索之Can you solve this equation?——hdu2199

2024-07-02 08:54:46   224人阅读

Can you solve this equation?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7507    Accepted Submission(s): 3490

Problem Description
Now,given the equation 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y,can you find its solution between 0 and 100;
Now please try your lucky.
 
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has a real number Y (fabs(Y) <= 1e10);
 
Output
For each test case, you should just output one real number(accurate up to 4 decimal places),which is the solution of the equation,or “No solution!”,if there is no solution for the equation between 0 and 100.
 
Sample Input
2
100
-4
 
Sample Output
1.6152
No solution!
 
Author
Redow
 
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2199

这道题目刚开始以为是计算几何，
但是出在了搜索专题里，就知道用搜索来做。。。
然后分析是哪种搜索？
基础的BFS,DFS肯定不是，
连BFS都不是 双向BFS那就更不用想。
A*、IDA*  看着可能有点意思。。。
但是，别忘了还有二分搜索= =。
恩，这道题就是用二分来解。
控制一下精度，
对于精度判定（我的理解）：
我觉得是，用printf直接输出一个double型，一般输出到6位小数，
我觉得就是默认保留的六位小数，于是精度设定1e-6.
但YM说是因为：
题目要求保留四位小数，一般会往后扩充两位小数来预防进位等情况，所以保留6位小数。
反正这道题是保证六位小数了，
还有要吐槽的一点，刚开始没仔细看测试数据，就看到1.615几，然后就交了，
AC后发现我的输入100会得出1.6151...题目样例是6.6152  o(╯□╰)o。。。。

这算不算水过= =。。。
再有一点，这题目测试数据中没有边界的判定。。。就是当y为6或者 8XXXXXX。。（将X等于100带入式子得到的Y）

/**************************************
***************************************
*        Author:Tree                  *
*From :http://blog.csdn.net/lttree    *
* Title : Can you solve this equation?*
*Source: hdu 2119                     *
* Hint  : 二分搜索                    *
***************************************
**************************************/

#include <stdio.h>
#define EPS 1e-6
double jdz(double a)
{
    return a<0?-a:a;
}
double calcu( double x )
{
    return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
}
double binary_s( int y )
{
    double l,h,m;
    l=0,h=100;
    while( h-l>EPS )
    {
        m=(l+h)/2.0;
        if( calcu(m)>y )   h=m;
        else    l=m;
    }
    return (l+h)/2.0;
}
int main()
{
    int test,y;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&y);
        if( y<=6 || y>=calcu(100) )    printf("No solution!\n");
        else    printf("%.4lf\n",binary_s( y ) );
    }
    return 0;
}






联系
我们