二分是一種很有效的減少時間開銷的策略, 我覺得單列出二分專題有些不太合理, 二分應該作為一中優化方法來考慮

這幾道題都是簡單的使用了二分方法優化, 二分雖然看似很簡單, 但一不注意就會犯錯. 在寫二分時, 會遇到很多選擇題, 很多"分叉路口", 要根據實際情況選擇合適的"路"

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

?

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

Recommend

?

注意看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-10; 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_JUDGEfreopen("data.in", "r", stdin);#endifstd::ios::sync_with_stdio(false);std::cin.tie(0);double y;double x;double r,l;int t;cin>>t;while(t--){cin>>y;if(y<6||y>js(100)){cout<<"No solution!"<<endl;}else{l=0; r=100;double mid,res;while(l+eps<r){mid=(l+r)/2;if(y<js(mid)){r=mid;}else{l=mid;}}cout<<fixed<<setprecision(4)<<mid<<endl;}}return 0; }

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 100 200

Sample Output -74.4291 -178.8534

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-10; double fd(double x) {return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x; } int main() {#ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin);#endifstd::ios::sync_with_stdio(false);std::cin.tie(0);int t;double y;double l,r,mid;cin>>t;while(t--){cin>>y;l=0;r=100;while(r-l>eps){mid=(l+r)/2;if(fd(mid)>y){r=mid;}else l=mid;}cout<<fixed<<setprecision(4)<<6*pow(mid,7)+8*pow(mid,6)+7*pow(mid,3)+5*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 bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size. What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

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 3 3 4 3 3 1 24 5 10 5 1 4 2 3 4 5 6 5 4 2

Sample Output 25.1327 3.1416 50.2655

?

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[11000] ; int n , m ; double f(double x) { int k = (x+eqs) * 10000 ; x = k * 1.0 / 10000 ; return x ; } int solve(double x) { int i , j , num = 0 ; for(i = n-1 ; i >= 0 && (s[i]-x) > eqs ; i--) { j = s[i] / x ; num += j ; if( num >= m+1 )return 1 ; } if( num >= m+1 ) return 1 ; return 0 ; } 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 = 0 ; i < n ; i++) scanf("%lf", &s[i]) ; sort(s,s+n) ; for(i = 0 ; i < n ; i++) s[i] = s[i]*s[i]*PI ; low = 0 ; high = s[n-1] ; while( (high-low) > eqs ) { mid = (low+high)/2.0 ; if( solve(mid) ) { low = mid ; last = mid ; } else high = mid ; } printf("%.4lf\n", last) ; } } return 0; }

?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 1 2 3 1 2 3 1 2 3 3 1 4 10

Sample Output Case 1: NO YES NO

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=0;right=h-1;mid=(left+right)/2;while(left<=right){mid=(left+right)/2;if(LN[mid]==t)return 1;else if(LN[mid]>t)right=mid-1;else if(LN[mid]<t)left=mid+1;}return 0; } int main() {int i,j,count=1,q;__int32 L[K],N[K],M[K],S,n,m,l;while(scanf("%d%d%d",&l,&n,&m)!=EOF){int h=0;for(i=0;i<l;i++)scanf("%d",&L[i]);for(i=0;i<n;i++)scanf("%d",&N[i]);for(i=0;i<m;i++)scanf("%d",&M[i]);for(i=0;i<l;i++)for(j=0;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=0;i<S;i++){scanf("%d",&q);/*q即為題目中的x*/int p=0; /*p為標記，0為找不到，1為能找到*/for(j=0;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=1;break;}}if(!p) /*找不到a*/printf("NO\n");}}return 0; }

?

轉載于:https://www.cnblogs.com/liuzhanshan/p/6052289.html

總結

以上是生活随笔為你收集整理的HDU2199,HDU2899,HDU1969,HDU2141--（简单二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。