首页 > 其他 > 详细

二分1

时间:2020-02-23 22:42:59      阅读:27      评论:0      收藏:0      [点我收藏+]

标签:problem   std   前缀和   def   记录   通过   

二分题目中通常有暗示:

最大值最小/最小值最大 (在最之间取平衡点)

最靠近某个值(类似)

最小的能满足条件的代价

***寻找题目中具备的单调性,运用二分解决问题

 聪明的质检员  https://www.luogu.org/problemnew/show/ P1314

二分+前缀和(通常区间求值)
通过判断呢,W越大,sum越小,单调性具备。
看了题解,发现min1的初始值设定过小
#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define ll long long struct stone{ ll w,v; }st[200001]; ll n,m,s,min1=0x3f3f3f3f3f3f3f3f,max1=-1,mi=0x3f3f3f3f3f3f3f3f,sumw[200001],sumv[200010]; struct ma{ ll l,r; }q[200001]; int main() { cin>>n>>m>>s; for(int i=1;i<=n;i++) cin>>st[i].w>>st[i].v,mi=min(mi,st[i].w),max1=max(max1,st[i].w); for(int i=1;i<=m;i++) { ll l,r; cin>>q[i].l>>q[i].r; } ll left=mi-1,right=max1,mid; while(left<=right) 二分,列举W可能取值 { mid=(left+right)/2;
     memset(sumv,0,sizeof(sumv)),memset(sumw,0,sizeof(sumw)); 注意初始化
for(int i=1;i<=n;i++)前缀和计算w的个数 if(st[i].w>=mid) sumw[i]=sumw[i-1]+1,sumv[i]=sumv[i-1]+st[i].v; else sumw[i]=sumw[i-1],sumv[i]=sumv[i-1]; ll sum=0; for(int i=1;i<=m;i++) sum+=(sumw[q[i].r]-sumw[q[i].l-1])*(sumv[q[i].r]-sumv[q[i].l-1]); //q【i】.l 值也在区间内 min1=min(min1,abs(sum-s)); if(sum>s) left=mid+1; sum>s,可知,W过小,需要变大 else right=mid-1; } cout<<min1; return 0; }

P2678 跳石头

 洛谷
 
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 50010
long long sum[maxn],n,cont,m;
bool check(long long x)
{
    long long s=0;cont=0;
    for(int i=1;i<=n+1;i++) if(sum[i]-s<x) cont++;else s=sum[i];//大佬写的一个代码
    return cont>m;
}
int main()
{
    long long l,ans;
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++) cin>>sum[i];
    long long left=1,right=l;
    sum[n+1]=l;
    while(left<=right){
        long long mid=(left+right)/2;
        if(check(mid)) right=mid-1;else ans=mid,left=mid+1;//mid是当前可行解,需要记录下来
    }
    cout<<ans<<endl;
    return 0;
}

Vijos / 题库 /

隐形的翅膀

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define pre 0.6180339887498949
#define maxn 50000
long long length[maxn];
long long rig,lef,mid,n,min1,min2;
double mi,mx;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>length[i];
    sort(length+1,length+n+1);
    for(int i=1;i<=n;i++)
    {
        long long len=length[i];
        lef=1;rig=n;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            mi=(double)length[mid]/(double)len;
            if(fabs(mx-pre)>fabs(mi-pre)) mx=mi,min1=i,min2=mid;//刚开始将这段放到二分外面,wa。应该是在循环外面少考虑些情况。
            if(mi>pre) rig=mid-1;//通过对比,刚开始受之前做的一道题误导,外加自己记串了,刚开始是通过比较与黄金分割的差距,少考虑些情况
            else lef=mid+1;
        }
    }
    cout<<min(length[min1],length[min2])<<endl;
    cout<<max(length[min1],length[min2]);
    return 0;
}

 

 

 

 

 

 

 

 

二分1

标签:problem   std   前缀和   def   记录   通过   

原文:https://www.cnblogs.com/Showend/p/12339719.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号