HDU-2141(简单二分模板题目）
题意：给定三个有序整数序列A、B、C和一个整数X，你能否找到一组Ai、Bj、Ck满足等式：Ai+Bj+Ck = X。 输入：可有多组输入实例。第一行有三个整数L、M、N，第二行是序列A中的L个有序整数，第三行是序列B中的M个有序整数，第四行是序列C中的N个有序整数。第五行是整数S，表示有S个X需要计算。1<=L, N, M<=500, 1<=S<=1000. 所有整数均为32位整数。 输出：对每一组测试实例，首先要输出“Case d:”，其中d为测试实例的序号，然后根据是否满足等式，输出NO（不满足），或YES（满足）。
#include<iostream> #include<algorithm> #include<set> using namespace std; #define maxn 505 int a[maxn]; int b[maxn]; int c[505]; int s[1010]; int sum[505*505]; int main() { int L,M,N,T; int h=0; while(~scanf("%d%d%d",&L,&M,&N)) { h++; for(int i=0;i<L;i++) scanf("%d",&a[i]); for(int i=0;i<M;i++) scanf("%d",&b[i]); for(int i=0;i<N;i++) scanf("%d",&c[i]); scanf("%d",&T); for(int i=0;i<T;i++) scanf("%d",&s[i]); int k=0; for(int i=0;i<L;i++) for(int j=0;j<M;j++) { sum[k++]=a[i]+b[j]; } sort(sum,sum+k); cout<<"Case "<<h<<":"<<endl; for(int i=0;i<T;i++) { int flag=0; for(int h=0;h<N;h++) { flag=binary_search(sum,sum+k,s[i]-c[h]); if(flag) break; } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } }题目思路：二分法，但是3个for循环的二分肯定会超时，所以数学式子换成：Ai+Bj=X-Ck;用一个数组存Ai+Bj,然后采用一个for循环循环Ci，寻找是否存在满足等式的情况。
HDU 1425 简单题
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 1000010; int a[maxn]; int cmp(int a,int b) { return a>b; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1,cmp); for(int i=1;i<=m;i++) { if(i>1)printf(" "); printf("%d",a[i]); } printf("\n"); } return 0; }poj 1064 Cable master
1.题意：
给定一系列长度的电缆，需要截取成等长的K份，求所能截取的最大长度值
2.题目思路：
这道题很明显是需要处理精度，二位小数，把问题简化，乘100化成整数，0.01变成1，求答案时只需要再除以100
所能截取的最大长度值原本是在1.00~max(这里的max值是给定一系列长度的电缆的电缆长度最大值）ps:由于这里的精度是0.01，则这里长度的增量为0.01，乘以100后，长度的增量为1
使用二分法：min=1,max,mid=(min+max)/2;
在长度里面找件数，看件数是否达标
寻找件数的代码：int t=0;//t为件数
for（int i=0;i<n;i++）//n件物品
{
t+=a[i]/mid;
}
3.解决代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define maxn 10000005 int a[maxn]; int main() { int n,m; int high,low,mid; while(scanf("%d%d",&n,&m)!=EOF) { int Max=0; double l; for(int i=0;i<n;i++) { cin>>l; a[i]=l*100; Max=max(Max,a[i]); } high=Max; low=1; int len=0; while(low<=high) { int t=0;//件数 mid=(high+low)/2; for(int i=0;i<n;i++) { t+=a[i]/mid; } if(t<m)//件数不足，说明长度取大了 { high=mid-1; } if(t>=m) { low=mid+1; len=max(len,mid); } } printf("%.2lf",(double)(len/100.0)); } return 0; }hdu 4430
1.题意
给出n，让n满足下列表达式：k^1+k^2+...+k^r=n. 且r*k要最小。(ps: And it's optional to place at most one candle at the center of the cake. 所以k^0（即1）可有可无。
2.题目思路
题目中涉及的变量的范围：k ≥ 2，r ≥ 1，18 ≤ n ≤ 10 12.利用等比数列的求和公式可得r的范围：1<=r<=40
我们可以枚举r，对k进行二分，判断sum与n的关系。（对k二分，是由于这里假设知道r，但很难得出k（k的区间为单调区间），而k是固定的，过程中求出的sum（函数关系）也是单调性的），所以我们可以用二分），另外枚举r是必须的，我们不知道哪个r*k最小。
假设该题我们不从r枚举开始，而是从k入手算r，时间复杂度太高了，k枚举（2到n循环）一定会超时，所以考虑之后我们只能从另一个变量r入手。
3.题目代码
#include<iostream> #include<cmath> using namespace std; #define inf 0x7f7f7f7f long long n,k,r,ll,rr,minx,mid; long long solve(long long mid,int i) { long long sum=0,ans=1; for(int j=1;j<=i;j++) { if(sum>n||n/ans<mid) { sum=n+1; break; } ans*=mid,sum+=ans; } if(sum==n||sum==n-1) { if(mid*i<k*r)//取k*r的最小值 { k=mid,r=i; } else if(mid*i==k*r&&i<r)//同样为最小，r小为第二判断 { k=mid,r=i; } return sum; } return sum; } int main() { while(~scanf("%lld",&n)) { r=1,k=n-1;//这里的k如果是n，答案会错误 //二分法求k的最大值 for(int i=2;i<=40;i++)//利用等比求和公式可得k的范围是2到40 { ll=2,rr=pow(n,1.0/r); while(ll<=rr) { mid=(ll+rr)/2; long long sum=solve(mid,i); if(sum>n||sum<0) rr=mid-1; else ll=mid+1; } } cout<<r<<" "<<k<<endl; } }HDU-2899
1.题意
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) ，给定y，求最小的F(x)值。
2.分析
求最小的F(x)值就是求x，这类的数学题目一般会想到二分，二分的变量只能是x(毕竟这里的y是常量，不可能作为二分的变量），那我们二分的关系是什么？（二分的关系即用来改变l与r的大小，二分的关系一定是单调的），按照一般思路我们会直接采用F(x)的值，但是F(x)不是单调性的，而我们要求最小值就会想到导函数g(x)。
if(g(0)>0)最小的导数值都大于0，说明f(x)单调递增,所以最小值在x=0取得
if(g(100)<0)最大的导数值都小于0，说明f(x)单调递减,所以最小值在x=100取得
导数有大于0小于0两种情况，最小值就在导数为0的时候获得
所以我们二分关系采用导数的值，因为导数值是单调递增的。
3.题目代码：
#include<iostream> #include<cmath> using namespace std; double y,x; #define eps 1e-10 double f(double x) { return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-x*y; } double g(double x) { return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lf",&y); if(g(100)<=y)//说明单调递减 printf("%.4lf\n",f(100)); else if(g(0)>0) //说明单调递增 printf("0"); else { double mid,r=100,l=0,minx=0; while(r-l>=eps) { mid=(l+r)/2; if(g(mid)>0) r=mid; else l=mid; } printf("%.4lf\n",f(mid)); } } }HDU-1969
题意：
给出T(案例数量），n（派的数量）(n>=1) ，f(朋友的数量）(f<=10000)，给出n个ri(1<=ri<=10000,1<=i<=n)，h=1,问每个人所得派的体积最大为多少，注意分派时人数是1(自己）+f，另外每个人的派不能是几个，必须是完整的一个。
分析：使用派的体积进行二分，所分得的人数作为二分关系
代码：
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define eps 1e-5 #define PI acos(-1.0) #define maxn 10011 double a[maxn]; int n,f; int solve(double x) { int t=0; for(int i=0;i<n;i++) { t=t+(int)(a[i]/x); } return t; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&f); f=f+1;//加上自己 double maxt=0; double l=0,r=0,mid; for(int i=0;i<n;i++) { scanf("%lf",&a[i]); a[i]=a[i]*a[i]*PI; if(maxt<a[i]) maxt=a[i]; } r=maxt; while(r-l>=eps) { mid=(l+r)/2; if(solve(mid)>=f)//说明小了 { l=mid; } else r=mid; } printf("%.4lf\n",l); } }POJ-3104（洗衣服）
题目思路： 此题的思路是：二分时间 ，假设时间 为 t，那么含水量小于或等于 t 的衣服直接风干就行了，不需考虑，设含水量大于 t 的第i件衣服所带的 水量 为Ai ，需要用吹风机的 次数 为 X ，用于 风干 的时间为 Y，吹风机一分钟 能够 吹干的水量为 k,则可得到 以下两式 ： X + Y = t (总时间）； X + Y * k >= Ai （每件衣服干的判断条件）; 由以上两式可得 ： Y >= (Ai - t)/(k - 1) ，算出所有含水量大于 t 的衣服 的 最小的 Y ， 然后相加得到 sum ，再用 sum 与 t 比较 ，作为 二分中 上下界改变的条件 。具体用法的详解请看程序：
#include<iostream> #include<algorithm> #include<cmath> using namespace std; #define maxn 100010 int a[maxn]; long long sum; int n,k; bool check(long long val) { long long cnt=0; for(int i=0;i<n;i++) { if(a[i]-val<=0)//可以自然分干 continue; if(k==1)//k的作用相当于风干 return false; cnt+=(a[i]-val+k-2)/(k-1);//cnt为所花时间 向上取整 if(cnt>val) return false; } return true; } int main() { string str; int t=1; while(~scanf("%d",&n)){ sum=0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); sum+=a[i]; } sort(a,a+n); scanf("%d",&k); sum=(sum+k-1)/k; long long l=0,r=sum,mid;//l与r表示时间 long long minx=r+1; while(l<=r){ mid=(l+r)/2; if(check(mid)==true)//表示可以全弄完 { if(minx>mid) minx=mid; r=mid-1; } else //把时间弄长 l=mid+1; } printf("%lld\n",minx); } }poj 3045 难度等级中等
题意：某摆放情况的奶牛最大风险为fmax，有很多种摆放情况，就有很多的fmax，我们需要求出最小的fmax.
我们这里需要求的是安排一个最好的序列，使它的最大风险都最小（以最小化风险的方式给出所有奶牛的最大风险）
解题思路：这道题也是最小最大值的问题，就是在最优的情况下求出里面最差的那个a[i]。
确定二分变量（一般就是题意需要求的东西），二分边界，solve()
首先我们知道二分变量是fmax，变量边界：l=0-s_max ; (最小风险肯定是放在顶层的奶牛） r=sum_w-min_w-min_s;（最大风险就是最大总和重量（该奶牛所受风险是不会含自己重量）-最小s
solve()这个是判断mid（所测最大风险）是否能 大于等于 每头奶牛的风险，即没有奶牛所受的风险比mid大
对于最底层的奶牛i，风险= sum_w-wi-si = sum_w-(wi+si) ,受的最小风险肯定是,sum_w-max(wi+si)
对于不是最底层的奶牛t而言：sum_w-(w1+w2+...+wt)-st =sum_w-(w1+w2+...+w(t-1))-(wt+st) 受的最小风险肯定是sum_w-(w1+w2+...+w(t-1))-max(wt+st) (w1+w2+...+w(t-1))这个是位于第t头牛下面所有奶牛的重量
我们可以从底层往顶层看，一步步固定奶牛就可以确定最优的情况（每头牛所受风险最小）
使用结构体就能知道max(wt+st)的wt的值，另外如果我们这里使用三个数组的话，因为我们对sumws进行排序，并不能知道它的wt是多少，只能知道i与sumws，所以我们采用结构体。
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; #define maxn 50010 #define maxs 1000000010 int n; long long sum_w; int min_w,min_s,max_s; struct node{ int w; int s; int sum;//w与s的总和 }; node mynode[maxn]; int cmp(node a,node b)//降序排序 { return (a.sum>b.sum); } int solve(long long mid) { if((sum_w-mynode[0].sum)>mid)//第一层 return 0; long long ww=0; for(int i=1;i<n;i++) { ww+=mynode[i-1].w; if((sum_w-ww-mynode[i].sum)>mid) return 0; } return 1; } int main() { scanf("%d",&n); sum_w=0; long long l=0,r=0,mid; max_s=-1*maxs; min_w=10001,min_s=maxs; for(int i=0;i<n;i++) { scanf("%d%d",&mynode[i].w,&mynode[i].s); mynode[i].sum=mynode[i].w+mynode[i].s; sum_w+=mynode[i].w; if(mynode[i].s>max_s) max_s=mynode[i].s; if(mynode[i].s<min_s) min_s=mynode[i].s; if(mynode[i].w<min_w) min_w=mynode[i].w; } sort(mynode,mynode+n,cmp); // for(int i=0;i<n;i++) // { // cout<<mynode[i].s<<mynode[i].w<<mynode[i].sum<<endl; // } l=-1*max_s; r=sum_w-min_s-min_w; long long ans=r+1; while(l<=r) { mid=(l+r)/2; if(solve(mid)==1)//说明可以 { if(ans>mid) ans=mid; r=mid-1; } else l=mid+1; } printf("%lld\n",ans); }poj 3579
题意:给你n个数，然后求它们两两相减的绝对值，然后找出这些绝对值的中位数。 解题思路：
先对n个数排序，那么最后的结果ans一定满足0<=ans<an-a1第二如何判断ans就是我们需要求的值，我们用二分进行逼近。l=0，r=an-a1，mid=（l+r）/2；二分如何逼近，如何判断我们要求的答案ans是在[l,mid]还是在[mid,r]部分呢? 很明显是原数组两个数相减的绝对值<mid个数，和>mid的个数进行比较。（绝对值的个数<mid,ans在[mid,r]区间，否则在[l,mid]区间内如何判段两数绝对值<mid的个数呢？ 如何求一个数减去a[0]的值小于mid的个数，我们找到一个a[i]>=a[0]+mid时最小的一个i，那么数组[0,i)值减去a[0],都小于mid，这样枚举i就可以求得两数相减差值小于mid的个数代码：
#include<iostream> #include<algorithm> using namespace std; int n,m; #define maxn 100010 int a[maxn]; int solve(int x) { int sum=0; for(int i=0;i<n;i++)//计算大于mid的数 { sum+=(lower_bound(a+i+1,a+n,x+a[i]+1)-(a+i+1)); } return sum<m;//如果为真，说明mid大了 } int main(){ while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } m=(n*(n-1)/2+1)/2;//M是记录中位数的位置(第几个) sort(a,a+n); int l=0,r=a[n-1]-a[0],mid; while(l<=r) { mid=(l+r)/2; if(solve(mid)==0) r=mid-1; else l=mid+1; } cout<<r+1<<endl;//这里只能写成这种形式 } }poj 2976
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int maxn=1e3+7; const double eps=1e-6; int n,k,a[maxn],b[maxn]; int solve(double mid) { //a/b=x+tmp a=x.b+tmp*b(tmp*b为方便直接写成tmp) a=x*b+tmp double tmp[maxn]; for(int i=0;i<n;i++) tmp[i]=a[i]-mid*b[i]; sort(tmp,tmp+n); double sum=0;//判断最后a[i]/b[i]与mid的误差tmp/b的误差总和是大于0还是小于0 for(int i=k;i<n;i++) sum+=tmp[i]; if(sum>=0.0) //说明mid取小 return 1; else return 0; //return (sum>=0.0);//说明比率不大 } int main() { while(~scanf("%d%d",&n,&k)) { if(n==0&&k==0) break; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&b[i]); double l=0,r=1.0,mid; while(r-l>eps) { mid=(l+r)/2; if(solve(mid))//说明可以解决 l=mid; else r=mid; } int ans=(int)(l*100+0.5); cout<<ans<<endl; } }
