目录
1.最大化最小值
poj3258：River Hopscotch
poj3273：Monthly Expense
poj3104：Drying
poj3045：Cow Acrobats
最大化平均值
poj2976：Dropping tests
poj3111：K Best
查找第k大的值
poj3579：Median
poj3685：Matrix
最小化第k大的值
poj2010：Moo University - Financial Aid
poj3662：Telephone Lines
其他
poj1759：Garland
poj3484：Showstopper
1.最大化最小值
poj3258：River Hopscotch
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
int a[maxn],L,n,m;bool check(int d){int pre=a[0],cnt=0;for(int i=1;i<=n;i++){if(a[i]-pre<d){cnt++;continue;} pre=a[i];}if(cnt>m||a[n+1]-pre<d) return false;return true;
}int main(){scanf("%d%d%d",&L,&n,&m);a[0]=0,a[n+1]=L;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a,a+n+1);int l=0,r=L+1; //r的取值要比答案区间大点，所以这里+1 while(r-l>1){ //这里的答案区间 [l,r) ,所以二分到区间长度为1时，答案就出来了 int mid=l+(r-l)/2;if(check(mid)) l=mid;else r=mid;}printf("%d\n",l);return 0;
}
poj3273：Monthly Expense
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int INF=1e9+10;
int a[maxn],n,m;bool check(int d){int sum,p=1;for(int i=1;i<=m;i++){sum=a[p++];while(p<=n&&sum+a[p]<=d){sum+=a[p++];}if(p>n) return true;}return false;
}int main(){scanf("%d%d",&n,&m);int mx=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);mx=max(mx,a[i]);}int l=mx,r=INF,ans=mx; while(r-l>=0){ //这里的答案区间 [l,r] ,所以二分到区间长度为空时，答案就出来了 int mid=l+(r-l)/2;if(check(mid)){ans=mid;r=mid-1; }else l=mid+1;}printf("%d\n",ans);return 0;
}/*
7 5
10 10 10 10 10 10 101 1
10000
*/
poj3104：Drying
题解：可以想到对时间进行二分，但对于衣服风干的总时间无法预定。
大佬很详细的思路，可以参考下~（在公式推导的地方有点问题，注意下就行）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
int a[maxn],n,k;/*设使用吹风机的时间为t,则每件衣服最多可以有mid-t的水可以风干，t*k+(mid-t)>=a[i],t>=(a[i]-mid)/(k-1)*/bool check(int mid){long long sum=0; //注意sum有可能超int，最好所有的变量都设为long long for(int i=n;i>0;i--){if(a[i]<=mid) break;sum+=ceil(1.0*(a[i]-mid)/(k-1));}return sum<=mid;
}int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+1+n);scanf("%d",&k);int ans=0;if(k==1) ans=a[n];else{int lb=0,ub=a[n]+1; //[lb,ub]while(ub-lb>=0){int mid=lb+(ub-lb)/2;if(check(mid)){ans=mid;ub=mid-1;//printf("ans=%d\n",ans);}else lb=mid+1;}}printf("%d\n",ans);}return 0;
}poj3045：Cow Acrobats
最大化平均值
poj2976：Dropping tests
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
const double eps=1e-6;
int a[maxn],b[maxn];
double y[maxn];
int n,k;bool check(double x){for(int i=0;i<n;i++){y[i]=a[i]-x*b[i];}sort(y,y+n);double sum=0;for(int i=n-1;i>=k;i--){sum+=y[i];}return sum>=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 lb=0,rb=1;while(fabs(rb-lb)>=eps){double mid=lb+(rb-lb)/2;if(check(mid)) lb=mid;else rb=mid;}printf("%.0f\n",100*lb);}return 0;
}
poj3111：K Best
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const double eps=1e-6;
int n,k;struct Node{int id;double v,w,y;bool operator < (const Node &a) const{if(y>=a.y) return true;return false;}
}res[maxn];bool check(double x){for(int i=1;i<=n;i++){res[i].y=res[i].v-x*res[i].w;}sort(res+1,res+1+n);double sum=0;for(int i=1;i<=k;i++){sum+=res[i].y;}return sum>=0;
}int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lf%lf",&res[i].v,&res[i].w);res[i].id=i;}double lb=0,rb=1e8;while(fabs(rb-lb)>=eps){double mid=lb+(rb-lb)/2;if(check(mid)) lb=mid;else rb=mid;}//printf("%f\n",lb);for(int i=1;i<=k;i++){if(i==1) printf("%d",res[i].id);else printf(" %d",res[i].id);} printf("\n");return 0;
}查找第k大的值
poj3579：Median
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
int a[maxn],n,m;int work(int x){int lb=1,ub=n,ans;while(lb<=ub){int mid=lb+(ub-lb)/2;if(a[mid]<=x){ans=mid;lb=mid+1;}else ub=mid-1;}return ans;
}bool check(int mid){ //在序列里，如果小于等于mid的数大于等于m个，true int cnt=0;for(int i=1;i<=n;i++){cnt+=work(a[i]+mid)-i;} return cnt>=m;
}int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);m=(n*(n-1)/2+1)/2; //中位数的位置sort(a+1,a+1+n);int ans=0,lb=0,ub=a[n]-a[1];while(lb<=ub){int mid=lb+(ub-lb)/2;if(check(mid)){ans=mid;ub=mid-1; }elselb=mid+1;}printf("%d\n",ans);}return 0;
}
poj3685：Matrix
最小化第k大的值
poj2010：Moo University - Financial Aid
poj3662：Telephone Lines
其他
poj1759：Garland
/*h[i]=(h[i-1]+h[i+1])/2-1;h[i+1]=2*(h[i]+1)-h[i-1];h[3]=2*h[2]+2-A证明：B的值与h[2]成正相关的。 只要证出这点，直接二分h[2]即可。 证明如下：（大概） 其实递推的过程中，h[i],h[i+1]化成只含h[2]和常数的式子，很容易看出h[i]中h[2]的系数大于h[i-1]中h[2]的系数，也就是h[i+1]=a*h[i]+b（a>0）
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
const double eps=1e-6;
int n;
double A,ans;bool check(double x){double a=A,b=x,tmp;for(int i=3;i<=n;i++){tmp=b;b=2*(b+1)-a;a=tmp;if(b<0) return false;}ans=b;return true;
}int main(){while(~scanf("%d%lf",&n,&A)){double lb=0,ub=A;while(ub-lb>=eps){double mid=lb+(ub-lb)/2;if(check(mid)) ub=mid;else lb=mid;}printf("%.2lf\n",ans);}return 0;
}
poj3484：Showstopper