POJ 2010 Moo University - Financial Aid 1759 Garland

二分中位数，然后另存一个数组，每次左边右边找，来判断下次的边界左移还是右移，或者符合条件，然后取一个最大值，再看有没有更大的，如果全都不符合，说明不存在，break。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<math.h>
typedef long long ll;
using namespace std;
ll r,l,mid,n,m,k,an;
struct zz{ll first;ll second;ll id;
}hh[200005];
zz hh1[200005];
ll dsa=-1;
bool bj=0;
bool C(zz x,zz y){return x.first<y.first;
}
bool D(zz x,zz y){return x.second<y.second;
}int main(){ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>n>>m>>k;r=n;for(int i=1;i<=m;i++){cin>>hh[i].first>>hh[i].second;}sort(hh+1,hh+1+m,C);for(int i=1;i<=m;i++){hh[i].id=i;}memcpy(hh1,hh,sizeof(hh));sort(hh1+1,hh1+1+m,D);an=n/2;l=1;r=m;while(l<r){mid=(l+r)/2;ll re=0,le=0;ll ans=hh[mid].second;for(int i=1;i<=m;i++){if(hh1[i].id<mid&&ans+hh1[i].second<=k&&le<an){le++;ans+=hh1[i].second;}if(hh1[i].id>mid&&ans+hh1[i].second<=k&&re<an){re++;ans+=hh1[i].second;}}if (le<an&&re>=an) {l=mid+1;}else if(re<an&&le>=an){r=mid;}else if(re>=an&&le>=an){dsa=max(dsa, hh[mid].first);l=mid+1;}else{break;}}printf("%lld\n",dsa);return 0;
}

第一个点确定，来获得B的最小高度。如果有第二个点，可以用公式往后推第三个点，再由第2 3点推4个，以此类推，可以推出B，然后对第二个点进行二分。

但是可能数据有问题，r-l>0.0001,样例过了，但是会WA，如果让它固定二分100次，就过了？

毕竟POJ

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<math.h>
typedef long long ll;
using namespace std;
double r,l,mid,n,m,k,an,hh;
bool check(double x){k=0x3f3f3f3f;double cn=m,dn=x;double f=0;an=n-2;while(an--){double g=2*dn+2-cn;cn=dn;dn=g;if(dn<0){return 0;}}hh=dn;return 1;
}
int main(){ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>n>>m;l=-1,r=1e8;an=n-2;for (int i =0; i<100; i++){mid=(l+r)/2;if(check(mid)){r=mid;}else{l=mid;}}printf("%.2lf\n",hh);return 0;
}