美文网首页
二分搜索

二分搜索

作者: 云中翻月 | 来源:发表于2019-06-28 17:19 被阅读0次

最大化最小值

POJ 3258: River Hopscotch
同noip跳石头。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
同noip跳石头。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
int a[maxn],l,n,m;
bool check(int mid){
    int sum=0,dis=0;
    for(int i=2;i<=n;i++){
        dis+=a[i]-a[i-1];
        if(dis<mid)sum++;
        else dis=0;
    }
    return sum<=m;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("River Hopscotch.in","r",stdin);
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[++n]=0,a[++n]=l;
    sort(a+1,a+n+1);
//  for(int i=1;i<=n;i++) D(a[i]);
    int l=0,r=INF;
    while(l<r){
//      D(l);D(r);E;
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3273: Monthly Expense
最小化最大值。
从左往右check即可。预处理前缀和简化运算。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
最小化最大值。 
从左往右check即可。预处理前缀和简化运算。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,m,a[maxn],sum[maxn],maxa=0;
bool check(int mid){
//  if(mid<maxa) return false;
    int ans=1,last=0;
//  D(mid);E;
    for(int i=1;i<=n;i++){
        if(a[i]>mid) return false; //注意这里要特判 
        int expense=sum[i]-sum[last];
//      D(expense);E;
        if(expense>mid){
            ans++;last=i-1;
        }
    }
//  D(ans);E;
    return ans<=m;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Monthly Expense.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i],sum[i]=sum[i-1]+a[i];
        maxa=max(maxa,a[i]);
    }
//  check(100);
    int l=0,r=INF;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3104: Drying
不开long long会WA（原因未知），用了cin会TLE。（这两个坑坑了了我五六次提交）
剩下就很简单了，二分时间然后check吹风机使用的总时间是否<=mid即可。
具体地说，对于二分值mid，如果衣服i的含水量<=mid，则不用操作。
如果衣服i的含水量>mid，则设吹风机对衣服i吹了x秒。
则x满足不等式kx+(mid-x)>=a[i]，即x>=(a[i]-mid)/(k-1)。
也就是说，对于衣服i，需要吹ceil((a[i]-mid)/(k-1))秒。
ps:注意这里k-1可能为0，所以要特判k=1的情况。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
不开long long会WA（原因未知），用了cin会TLE。（这两个坑坑了了我五六次提交） 
剩下就很简单了，二分时间然后check吹风机使用的总时间是否<=mid即可。
具体地说，对于二分值mid，如果衣服i的含水量<=mid，则不用操作。
如果衣服i的含水量>mid，则设吹风机对衣服i吹了x秒。
则x满足不等式kx+(mid-x)>=a[i]，即x>=(a[i]-mid)/(k-1)。 
也就是说，对于衣服i，需要吹ceil((a[i]-mid)/(k-1))秒。 
ps:注意这里k-1可能为0，所以要特判k=1的情况。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
ll n,a[maxn],k,maxa=0;
bool check(int mid){
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]<=mid) continue;
        if((a[i]-mid)%(k-1)==0) ans+=(a[i]-mid)/(k-1);
        else ans+=(a[i]-mid)/(k-1)+1;
    }
    return ans<=mid;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Drying.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),maxa=max(maxa,a[i]);
    cin>>k;
    if(k==1){
        cout<<maxa;return 0;
    }
    ll l=0,r=INF;
    while(l<r){
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1; 
    }
    cout<<r;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3045: Cow Acrobats
题解链接 https://www.cnblogs.com/wmrv587/p/3700452.html
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
https://www.cnblogs.com/wmrv587/p/3700452.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
struct node{
    int w,s;
    bool operator<(const node& h)const{return w+s<h.w+h.s;}
}a[maxn];
int n,W=0,ans=-INF;
int main() {
    ios::sync_with_stdio(false);
    //freopen("Cow Acrobats.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].s;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        ans=max(ans,W-a[i].s);
        W+=a[i].w;
//      D(W);
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

01分数规划

POJ 2976: Dropping tests
设答案为mid，二分答案。
具体check过程如下：
\frac{\sum{ai}}{\sum{bi}} \geq mid，则∑a_{i}-mid*∑b_{i}>=0
即\sum \left ( a_{i}-mid*b_{i} \right ) \geq 0，只要对a_{i}-mid*b_{i}排序后，取较大的n-k个，判断和是否大于等于0即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
设答案为mid，二分答案。
具体check过程如下：
∑ai/∑bi>=mid，则∑ai-mid*∑bi>=0
即∑(ai-mid*bi)>=0，只要对ai-mid*bi排序后，取较大的n-k个，判断和是否大于等于0即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-5;
int n,k;
double a[maxn],b[maxn],c[maxn];
bool check(double mid){
    for(int i=1;i<=n;i++) c[i]=a[i]-mid*b[i];
    sort(c+1,c+n+1);
    double sum=0;
    for(int i=k+1;i<=n;i++) sum+=c[i];
    return sum>=0;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Dropping tests.in","r",stdin);
    while(cin>>n>>k){
        if(n==0&&k==0) break;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        double l=0,r=1;//ai<=bi
        while(r-l>eps){
            double mid=(r+l)/2;
            if(check(mid)) l=mid;
            else r=mid;
        }
        cout<<(int)((l+0.005)*100)<<endl; //题目要求精确到0.001并四舍五入 
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3111: K Best
方法同Dropping tests。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
方法同Dropping tests。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-5;
int n,k;
struct node{
    double v,w,c;
    int id;
    bool operator<(const node& h)const{return c>h.c;}
}a[maxn],b[maxn];
bool check(double mid) {
    for(int i=1; i<=n; i++) b[i].c=a[i].v-mid*a[i].w,b[i].id=a[i].id;
    sort(b+1,b+n+1);
    double sum=0;
    for(int i=1; i<=k; i++){
        sum+=b[i].c;
    }
    return sum>=0;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("K Best.in","r",stdin);
    cin>>n>>k;
    for(int i=1; i<=n; i++) scanf("%lf%lf",&a[i].v,&a[i].w),a[i].id=i;
    double l=0,r=INF;
    while(r-l>eps) {
        double mid=(r+l)/2;
//      D(l);D(r);D(mid);E;
        if(check(mid)) l=mid;
        else r=mid;
    }
    for(int i=1;i<=k;i++) printf("%d ",b[i].id);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

第k大值

POJ 3579: Median
二分答案，然后用upper_bound来求绝对值差在mid以内的数对的个数即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
二分答案，然后用upper_bound来求绝对值差在mid以内的数对的个数即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],ans,l,r;
ll m;
ll check(int mid){ //返回绝对值差在mid以内的数对的个数 
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=(ll)(upper_bound(a+i+1,a+n+1,a[i]+mid)-(a+i+1));
//      D(l);D(r);D(i);D(mid);D(sum);E;
    }
    return sum;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Median.in","r",stdin);
    while(cin>>n){
        m=(ll)n*(n-1)/2;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]); //cin会TLE 
        sort(a+1,a+n+1);
        l=0,r=INF;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)>=(m+1)/2) r=mid;
            else l=mid+1;
            /*
            //不能这样写 反例
            4
            2 2 4 5 
            int mid=l+r+1>>1;
            if(check(mid)<=(m+1)/2) l=mid;
            else r=mid-1;
            */
        }
        cout<<r<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3685: Matrix
观察这个式子，可以发现j不变的情况下，随着i的增大，Aij也相应增大。
由这个受到启发：二分枚举第M小的数，然后按列寻找，找到第一个大于这个数的位置，就可以知道该列中有多少个数是大于这个数。
难点是二分范围和精度问题，因为用int结果WA无数次，最后一个个换掉，最后全部变成long long才过。
代码如下

/*

*/
#define method_2
#ifdef method_1
/*
打表用 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n=15,a[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    freopen("Matrix.in","r",stdin);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=i*i+100000*i+j*j-100000*j+i*j;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        E;
    }
    return 0;
}
#endif
#ifdef method_2
/*
观察这个式子，可以发现j不变的情况下，随着i的增大，Aij也相应增大。 
由这个受到启发：二分枚举第M小的数，然后按列寻找，找到第一个大于这个数的位置，就可以知道该列中有多少个数是大于这个数。
难点是二分范围和精度问题，因为用int结果WA无数次，最后一个个换掉，最后全部变成long long才过。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
ll n,T;
ll m;
ll cal(ll i,ll j){
    return i*i+100000*i+j*j-100000*j+i*j;
}
/*
ll check(ll now){ //求矩阵中有多少数字小于等于mid 
    ll sum=0;
    for(int i=1;i<=n;i++){ //枚举列 
        int l=0,r=n+1;
        while(l<r){
            int mid=l+r>>1;
            if(cal(mid,i)>=now) r=mid;
            else l=mid+1;
        }
        sum+=r;
    }
    return sum;
}
*/
ll check(ll now){ //求矩阵中有多少数字小于mid 
    ll sum=0;
    for(ll i=1;i<=n;i++){ //枚举列 
        ll l=1,r=n+1;
        while(l<r){
            ll mid=l+r>>1;
            if(cal(mid,i)>now) r=mid;
            else l=mid+1;
        }
        sum+=l-1;
    }
    return sum;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Matrix.in","r",stdin);
    cin>>T;
    while(T--){
        cin>>n>>m;
//      ll l=-100000ll*n,r=n*n+100000ll*n+n*n+n*n; //用这个紧的范围 耗时为[-INF,INF]的一半 
        ll l=-INF,r=INF; 
        while(l<r){
            /*
            ll mid=l+r>>1;
            if(check(mid)>=m) r=mid;
            else l=mid+1;
            */
            ll mid=l+r>>1;
            if(check(mid)<m) l=mid+1;
            else r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

最小化第k大值

POJ 2010: Moo University - Financial Aid
题解链接 https://www.jianshu.com/p/5765513ce5b4
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
将所有奶牛按照score升序排序后，从大向小一次尝试作为中位数是否可行即可。
为了提高对于每头奶牛判断的效率，用sum1[i]表示i左侧c/2头牛的最小aid和，可用一个大小固定为n/2的大根堆来求，每次与堆顶元素比较。
同理可以对称的定义sum2[i]。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,c,f,sum1[maxn],sum2[maxn];//sum1[i]表示i左侧c/2头牛的最小aid和 用一个大小固定为n/2的大根堆来求 每次与堆顶元素比较 
struct node{
    int s,aid;
    bool operator<(const node& h)const{return s<h.s;}
}cow[maxn];
priority_queue<int>q;
void pre1(){ 
    while(q.size()) q.pop();
    int sum=0,nowf; //堆中所有元素和 
    for(int i=1;i<=c;i++){
        sum1[i]=sum;
        if(q.size()) nowf=q.top();
        if(q.size()<n/2){
            q.push(cow[i].aid);
            sum+=cow[i].aid;
        }
        else{
            if(cow[i].aid<nowf){
                q.pop();
                q.push(cow[i].aid);
                sum=sum-nowf+cow[i].aid;
            }
        }
//      D(sum1[i]);
    }
}
void pre2(){
    while(q.size()) q.pop();
    int sum=0,nowf; //堆中所有元素和 
    for(int i=c;i>=1;i--){
        sum2[i]=sum;
        if(q.size()) nowf=q.top();
        if(q.size()<n/2){
            q.push(cow[i].aid);
            sum+=cow[i].aid;
        }
        else{
            if(cow[i].aid<nowf){
                q.pop();
                q.push(cow[i].aid);
                sum=sum-nowf+cow[i].aid;
            }
        }
//      D(sum2[i]);
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Moo University - Financial Aid.in","r",stdin);
    scanf("%d%d%d",&n,&c,&f);
    for(int i=1;i<=c;i++) scanf("%d%d",&cow[i].s,&cow[i].aid);
    sort(cow+1,cow+c+1);
    pre1();
    pre2();
    bool flag=false; 
    for(int i=c-n/2;i>=n/2+1;i--){ //从大到小依次枚举当前值能否作为中位数 
        if(cow[i].aid+sum1[i]+sum2[i]<=f){
            flag=true;
            cout<<cow[i].s;
            break;
        }
    }
    if(flag==false) cout<<-1;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3662: Telephone Lines
二分答案，设当前答案为mid。
将所有边的边权-mid后，权值<=0的边边权设为0，否则为1。
然后，从1到n跑最短路，如果最短路<=k，则满足条件。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
二分答案，设当前答案为mid。
将所有边的边权-mid后，权值<=0的边边权设为0，否则为1。
然后，从1到n跑最短路，如果最短路<=k，则满足条件。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int maxp=10000+5;
const int INF=0x3f3f3f3f;
int n,p,k,head[maxn],tot=1,vis[maxn];
deque<pii>q;
struct node{
    int from,to,c;
}edge[maxp<<1],edge1[maxp<<1];
void add(int from,int to,int c){
    edge[++tot].from=head[from],edge[tot].to=to,edge[tot].c=c;
    edge1[tot].from=head[from],edge1[tot].to=to;
    head[from]=tot;
}
void init(){
    while(q.size()) q.pop_front();
    q.push_back(make_pair(1,0));
    memset(vis,0,sizeof(vis));
}
int bfs(){
    init();
    while(q.size()){
        pii now=q.front();q.pop_front();
        int x=now.first,d=now.second;
        if(x==n) return d;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge1[i].from){
            int y=edge1[i].to,c=edge1[i].c;
            if(c==0) q.push_front(make_pair(y,d));
            else q.push_back(make_pair(y,d+1));
        }
    }
    return INF;
}
bool check(int mid){
    for(int i=2;i<=2*p+1;i++){
        edge1[i].c=edge[i].c-mid;
        if(edge1[i].c<=0) edge1[i].c=0;
        else edge1[i].c=1;
    }
    return bfs()<=k;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Telephone Lines.in","r",stdin);
    cin>>n>>p>>k;
    int from,to,c;
    for(int i=1;i<=p;i++) cin>>from>>to>>c,add(from,to,c),add(to,from,c);
//  D(tot);
    int l=0,r=INF;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    r==INF?cout<<-1:cout<<r;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

其他二分搜索

POJ 1759: Garland
h_i=2*h_i-1-h_i-2+2
因此可以根据h_1和h_2递推。
又因为递推式关于h_i-1单调递增，所以h_2越小，答案就越小，所以二分h_2即可。
注意天坑：n=3时，答案是-0.00，要纠正为0.00。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
h_i=2*h_i-1-h_i-2+2
因此可以根据h1和h2递推。
又因为递推式关于hi-1单调递增，所以h_2越小，答案就越小，所以二分h2即可。 
注意天坑：n=3时，答案是-0.00，要纠正为0.00。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-5;
int n;
double A;
double cal(double mid){ //计算B 
    double pre1=A,pre2=mid,temp;
    for(int i=3;i<=n;i++){
        temp=2*pre2-pre1+2;
        pre1=pre2;pre2=temp;
    }
    return temp;
}
bool check(double mid){
    double pre1=A,pre2=mid,temp;
    for(int i=3;i<=n;i++){
        temp=2*pre2-pre1+2;
        if(temp<0) return false;
        pre1=pre2;pre2=temp;
    }
    return true;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Garland.in","r",stdin);
    cin>>n>>A;
    double l=0.0,r=(double)INF;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    double ans=cal(l);
    if(ans<eps) ans=0.00; //天坑 n=3时 答案是-0.00 要纠正为0.00 
    printf("%.2lf",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3484: Showstopper
原理同防线。
由于只有一个点有奇数个数，则如果某个点的前缀和为奇数，
这个位置一定在左边，否则在右边，二分位置即可。
注意输入很恶心。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
原理同防线。
由于只有一个点有奇数个数，则如果某个点的前缀和为奇数，
这个位置一定在左边，否则在右边，二分位置即可。 
注意输入很恶心。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20000+5; //poj上有人手测出的二分范围 
const int maxp=100+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
char a[maxn];
int n;
vector<ll>x,y,z;
bool read(){
    bool flag=false;
    x.clear();y.clear();z.clear();
    while(gets(a)){
        if(strlen(a)==0){
            if(flag==true) break;
            else continue;
        }
        ll xx,yy,zz;
        sscanf(a,"%lld%lld%lld",&xx,&yy,&zz);
        flag=true;
        x.push_back(xx);y.push_back(yy);z.push_back(zz);
    }
    n=x.size();
    return flag;
}
ll check(ll mid){ //求1~mid的前缀和 
    ll ans=0;
    for(int i=0;i<n;i++){
        if(x[i]>mid) continue;
        ans+=(min(y[i],mid)-x[i])/z[i]+1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Showstopper.in","r",stdin);
    while(read()){
        ll l=0,r=INF;
        while(l<r){
            ll mid=l+r>>1;
            if(check(mid)&1) r=mid;
            else l=mid+1;
        }
        if(r==INF) cout<<"no corruption"<<endl;
        else{
            cout<<r<<" ";
            int tot=0;
            for(int i=0;i<n;i++){
                if(r<=y[i]&&r>=x[i]){
                    if((r-x[i])%z[i]==0) tot++;
                }
            }
            cout<<tot<<endl;
        }
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

相关文章

  • Algorithm进阶计划 -- 二分搜索

    二分搜索二分搜索模板二分搜索运用 1. 二分搜索模板 二分搜索（二分查找）也称折半查找（Binary Search...

  • 算法-二分搜索算法

    算法：二分搜索算法（折半查找算法）时间复杂度： 二分搜索算法概述 二分搜索算法伪代码 二分搜索算法实现 二分搜索算...

  • 搜索算法

    顺序搜索 二分搜索

  • 二分搜索（Binary_Search）

    1. 二分搜索是什么？ 二分搜索（英语：binary search），也叫折半搜索（英语：half-interva...

  • AVL 树

    一：什么是 AVL 树？ 在我的上一篇文章《二分搜索树与二分查找法》中，详细介绍了二分搜索树这种数据结构。二分搜索...

  • 二分算法-LeetCode 69

    二分算法-LeetCode 69 二分算法 二分算法模板, 二分搜索即搜索一个数，如果存在，返回其索引，否则返回-...

  • Pearls9. 代码调优

    [TOC] 问题：在包含1000个整数的表中进行二分搜索： 二分搜索的调优 说明：在二分搜索中通常不需要代码调优 ...

  • Pearls4 编写正确的程序

    4.1 二分搜索

  • 手敲数据结构——使用二分搜索树实现Set

    关于实现二分搜索树，可以看前面的文章 手敲数据结构——二分搜索树

  • 分治算法（二分搜索）

    每日一言 : 当我们真正热爱这世界时，我们才真正生活在这世上。——泰戈尔 二分搜索 什么是二分搜索 二分搜索又叫二...

网友评论

      本文标题：二分搜索

      本文链接：https://www.haomeiwen.com/subject/nyzqqctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|二分搜索|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！