二分是一种很有效的减少时间开销的策略, 我觉得单列出二分专题有些不太合理, 二分应该作为一中优化方法来考虑
这几道题都是简单的使用了二分方法优化, 二分虽然看似很简单, 但一不注意就会犯错. 在写二分时, 会遇到很多选择题, 很多"分叉路口", 要根据实际情况选择合适的"路"
HDU2199
Can you solve this equation?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1195 Accepted Submission(s): 565
Now please try your lucky.
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);
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.
100
-4
No solution!
|
|
注意看AC代码,循环的条件是 l+eps<r ,不能用 f(mid)==res 否则会一直循环下去(注意看循环内部, 有可能边界(l或r)就为正确的值, 这样的话永远不会搜索到)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
#define INF 0x7ffffff
#define MAXN 10000
using namespace std;
const double eps=1e-;
double js(double x)
{
return 8.0*x*x*x*x + 7.0*x*x*x + 2.0*x*x + 3.0*x + 6.0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie();
double y;
double x;
double r,l;
int t;
cin>>t;
while(t--){
cin>>y;
if(y<||y>js()){
cout<<"No solution!"<<endl;
}
else{
l=; r=;
double mid,res;
while(l+eps<r){
mid=(l+r)/;
if(y<js(mid)){
r=mid;
}
else{
l=mid;
}
}
cout<<fixed<<setprecision()<<mid<<endl;
}
}
return ;
}
HDU2899
Strange fuction
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 666 Accepted Submission(s): 549 |
|
Problem Description
Now, here is a fuction:
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) Can you find the minimum value when x is between 0 and 100. |
|
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 only one real numbers Y.(0 < Y <1e10) |
|
Output
Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100. |
|
Sample Input
2 |
|
Sample Output
-74.4291 |
|
Author
Redow
|
|
Recommend
lcy
|
和上一道题一模一样,只不过这道题目拐了个弯, 需要进行求导
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
#define INF 0x7ffffff
#define MAXN 10000
using namespace std;
const double eps=1e-;
double fd(double x)
{
return *pow(x,)+*pow(x,)+*pow(x,)+*x;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie();
int t;
double y;
double l,r,mid;
cin>>t;
while(t--){
cin>>y;
l=;
r=;
while(r-l>eps){
mid=(l+r)/;
if(fd(mid)>y){
r=mid;
}
else l=mid;
}
cout<<fixed<<setprecision()<<*pow(mid,)+*pow(mid,)+*pow(mid,)+*mid*mid-y*mid<<endl;
}
}
HDU1969
Pie
| Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 939 Accepted Submission(s): 348 |
|
Problem Description
My birthday is coming up and traditionally I'm serving pie. Not
just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though. My friends are very annoying and if one of them gets a What is the |
|
Input
One line with a positive integer: the number of test cases. Then for each test case:
---One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends. ---One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies. |
|
Output
For each test case, output one line with the largest possible
volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3). |
|
Sample Input
3 |
|
Sample Output
25.1327 |
|
Source
NWERC2006
|
|
Recommend
wangye
|
这道题没有固定的函数关系, 每一个待定的面积值都要去除每块pie的面积, 为了加快搜索到结果的速度, 可以采用二分的方法(可分成的块数大体上是相对于面积递增的)
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
#define PI 3.1415926535898
#define eqs 1e-5
double s[] ;
int n , m ;
double f(double x)
{
int k = (x+eqs) * ;
x = k * 1.0 / ;
return x ;
}
int solve(double x)
{
int i , j , num = ;
for(i = n- ; i >= && (s[i]-x) > eqs ; i--)
{
j = s[i] / x ;
num += j ;
if( num >= m+ )return ;
}
if( num >= m+ ) return ;
return ;
}
int main()
{
int t , i , k ;
double low , mid , high , last ;
while( scanf("%d", &t) != EOF )
{
while(t--)
{
scanf("%d %d", &n, &m) ;
for(i = ; i < n ; i++)
scanf("%lf", &s[i]) ;
sort(s,s+n) ;
for(i = ; i < n ; i++)
s[i] = s[i]*s[i]*PI ;
low = ;
high = s[n-] ;
while( (high-low) > eqs )
{
mid = (low+high)/2.0 ;
if( solve(mid) )
{
low = mid ;
last = mid ;
}
else
high = mid ;
}
printf("%.4lf\n", last) ;
}
}
return ;
}
HDU2141
Can you find it?
| Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000 K (Java/Others) |
| Total Submission(s): 1157 Accepted Submission(s): 373 |
|
Problem Description
Give you three sequences of numbers A, B, C, then we give you a
number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X. |
|
Input
There are many cases. Every data case is described as followed:
In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers. |
|
Output
For each case, firstly you have to print the case number as the
form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO". |
|
Sample Input
3 3 3 |
|
Sample Output
Case 1: |
|
Author
wangye
|
|
Source
HDU 2007-11 Programming Contest
|
|
Recommend
威士忌
|
一样的题目, 不多说了
代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
#define K 505
int LN[K*K];
int BinarySearch(int LN[],int h,int t)/*二分查找*/
{
int left,right,mid;
left=;
right=h-;
mid=(left+right)/;
while(left<=right)
{
mid=(left+right)/;
if(LN[mid]==t)
return ;
else if(LN[mid]>t)
right=mid-;
else if(LN[mid]<t)
left=mid+;
}
return ;
}
int main()
{
int i,j,count=,q;
__int32 L[K],N[K],M[K],S,n,m,l;
while(scanf("%d%d%d",&l,&n,&m)!=EOF)
{
int h=;
for(i=;i<l;i++)
scanf("%d",&L[i]);
for(i=;i<n;i++)
scanf("%d",&N[i]);
for(i=;i<m;i++)
scanf("%d",&M[i]);
for(i=;i<l;i++)
for(j=;j<n;j++)
LN[h++]=L[i]+N[j];/*合并L和N*/
sort(LN,LN+h); /*对LN数组排序*/
scanf("%d",&S);
printf("Case %d:\n",count++);
for(i=;i<S;i++)
{
scanf("%d",&q);/*q即为题目中的x*/
int p=; /*p为标记，0为找不到，1为能找到*/
for(j=;j<m;j++)
{
int a=q-M[j]; /*因为L[i]+N[j]+M[k]==q，所以q-M[k]=LN[h]*/
if(BinarySearch(LN,h,a)) /*在LN数组中查找到a*/
{
printf("YES\n");
p=;
break;
}
}
if(!p) /*找不到a*/
printf("NO\n");
}
}
return ;
}