二分题单

2023-11-23 16:19:34

w佬 的二分题单 link

整数二分

跳石头

思路

首先序列是单调的，然后我们可以枚举每个maxd，求可以满足条件的maxd中的最大值，这时候我们就想，可以二分吗？

mid右边，不满足条件。（相当于跳跃距离的区间变小）

mid左边，满足条件。（区间变大）

满足二分。

check

int mid=r+l+1>>1;
if(check(mid))l=mid;
else r=mid-1;

时间复杂度 \(O(nlogn)\)

代码

import java.util.*;
import java.io.*;
class Main
{
    static int N=50010 ,L,n,m;
    static int[] a=new int[N];
    
    static boolean check(int maxd)
    {
        int cnt=0,last=0;
        for(int i=1;i<=n+1;i++)
        {
            if(a[i]-last<maxd)
                cnt++;
            else last=a[i];
        }
        return cnt<=m;
    }
    
    public static void main(String[]args)
    {
        Scanner in=new Scanner(System.in);
        L=in.nextInt(); n=in.nextInt(); m=in.nextInt();
        a[n+1]=L;
        for(int i=1;i<=n;i++)
            a[i]=in.nextInt();
            
        int l=0,r=(int)1e9;
        while(r>l)
        {
            int mid=r+l+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        
        System.out.println(l);
    }
}

题意

数轴上面有n座城市，m座塔，塔的信号可以覆盖两边不超过 r ，求信号将城市全部覆盖掉，最小的 r的是多少。

思路

\(r\) 跟 塔与城市之间的距离有关系。也就我们可以让城市由它最近的塔来传输信号，这样一来，最近的，那么我们该怎么处理呢 ?

题目说 坐标都是递增的，那我们找点，就可以用二分，假如我们要找它的右塔，那么就是第一个 >= 它的坐标。

接下来是边界，如果城市的右边没有塔了，也就是我们需要定义一个返回值，来说明没有塔的右边没有塔了 ，那我们就将二分的右边界设为一个特定值。

如果说左边没有塔了，也就是右边只有一个塔，这时候我们只需要将\(r\)​变为dist[1]- coordine[i]

如果我们有塔，我们应取左右两边 \(r\) 的最小值

时间复杂度 \(O(nlogn)\)

代码

import java.util.*;
import java.io.*;
public class Main
{
    static int N=100010,n,m,INF=0x3f3f3f3f;
    static int[] a=new int[N],b=new int[N];
    static String[] ss;
    static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    static int xIt(String x)
    {  return Integer.parseInt(x); }
    
    static String[] read()throws IOException
    {return in.readLine().split(" ");}
    
    static int log(int x)
    {
		int r=m+1,l=1;
          while(r>l)
          {
              int mid=l+r>>1;
              if(b[mid]<x) l=mid+1;
              else r=mid;
          }
        return l;
    }
    
    public static void main(String[]args)throws IOException
    {
		ss=read();
        n=xIt(ss[0]);m=xIt(ss[1]);
        
        ss=read();
        for(int i=1;i<=n;i++)
            a[i]=xIt(ss[i-1]);
        ss=read();
       for(int i=1;i<=m;i++)
           	b[i]=xIt(ss[i-1]);
        int ans=-INF;
       for(int i=1;i<=n;i++)
       {
           int index=log(a[i]);
           if(index>m) ans=Math.max(ans,a[i]-b[index-1]);
           else if(index==1) ans=Math.max(ans,b[1]-a[i]);
           else ans=Math.max(ans,Math.min(b[index]-a[i],a[i]-b[index-1]));
           		
       }
		System.out.println(ans);
    }
}

思路

将二维拆为两个一维。记录第i 个操作能到的下标，也就是记录每次操作，对x,y 的贡献

例如 U 就是对y的贡献为1对x 的贡献为0 。

因为我们一直对区间求操作，那么应该想到前缀和。这时候前缀和表示就是就前 i 个操作我所能到达的点。

那么什么时候到达不了呢？

进行 n 次操作后我们从(0,0) 可以移动n格。

当 |x|+|y|>n 时 我们无法进行n次操作到达 (x,y)

我们可以发现一个性质，就是我们每走一步，我们就会改变 x+y的奇偶性。

当 x+y 与 n 的奇偶性不同时，也就是说我们需要操作的次数m 和n无法通过其他操作来弥补那些空挡也就是 UD这样的兜圈操作

时间复杂度 \(o(nlogn)\)

代码

import java.util.*;
import java.io.*;
 public class Main
{
    static int N=200010,xs,ys,n,INF=0x3f3f3f3f;
    static int[] x=new int[N],y=new int[N];
    static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out=new PrintWriter(System.out);
    static String[] ss;
    static char[] s;
    static String[] read()thro t(" ");}
    static int xIt(String x)
    {return Integer.parseInt(x);}
    
    
    static boolean check(int len)
    {
        for(int l=1;l+len-1<=n;l++)
        {                                
            int r=l+len-1;
            if(Math.abs(xs-(x[n]-x[r]+x[l-1]))+Math.abs(ys-(y[n]-y[r]+y[l-1]))<=len) return true;
        }
        return false;
    }
    
    public static void main(String[]args)throws IOException
    {
        ss=read();
        n=xIt(ss[0]);
        s=in.readLine().toCharArray();
        ss=read();
        xs=xIt(ss[0]);ys=xIt(ss[1]);
        
        for(int i=1;i<=n;i++)
        {
           if(s[i-1]=='U') {y[i]=y[i-1]+1;x[i]=x[i-1];}
            else if(s[i-1]=='D') {y[i]=y[i-1]-1;x[i]=x[i-1];}
            else if(s[i-1]=='L') {y[i]=y[i-1];x[i]=x[i-1]-1;}
            else  {y[i]=y[i-1];x[i]=x[i-1]+1;}                
        }
        
        int cn=Math.abs(xs)+Math.abs(ys);
        if(cn>n||Math.abs(n-cn)%2==1)    
                System.out.println("-1");
        else
        {   
            int l=0,r=n,ans=INF;
            while(r>l)
            {
                int mid=r+l>>1;
                if(check(mid))
                {
                    ans=Math.min(ans,mid);
                    r=mid;
                  }
                else l=mid+1;
            }
            if(l==n) System.out.println(n);
            System.out.println(ans);
        }
        
    }
}

浮点数二分

最佳牛围栏 link

题意

就是找 一段连续的区间 使其$${\sum_l^r cow_i} \over r-l$$ 最大 这也就是 平均值

思路

前缀和维护来快速求区间和，这不过我们只是要找出来这个平均值，也就是求\(\frac {\sum_l^r cow_i} {r-l} - {avg} >=0\)

我们将$\frac {\sum_l^r cow_i-avg} {r-l} >=0 $

\({\sum_l^r （cow_i-avg）} >=0\)

\(\exists {\sum_0^r （cow_i-avg）}-{\sum_0^l （cow_i-avg）} >=0\)

也就是我们求前缀和的时候 给每一项将去\(avg\)

因为是$$\exists$$ 所以我们求出 $${\sum_0^l （cow_i-avg）} $$ 的最小值

连续的区间，所以我们只需遍历一遍就可以了，顺带着维护这个最小值

当然还有\(r-l>=F\)​​

时间复杂度 \(O(nlogn)\)

代码

import java.util.*;
import java.io.*;
class Main
{
    static int N=100010,n,F;
    static int[] a=new int[N];
    static double[] sum=new double[N];
    
    static int get(String s)
    {
        return Integer.parseInt(s);
    }
    
    static boolean check(double avg)
    {
        for(int i=1;i<=n;i++) 
            sum[i]=sum[i-1]+a[i]-avg;
        double mins=0x3f3f3f3f;
        for(int i=F;i<=n;i++)
        {
            mins=Math.min(mins,sum[i-F]);
            if(sum[i]-mins>=0) return true;
        }
        return false;
    }
    
    public static void main(String[]args)throws IOException
    {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        String[] ss=in.readLine().split(" ");
        n=get(ss[0]);F=get(ss[1]);
        double r=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=get(in.readLine().split(" ")[0]);
            r=Math.max(r,a[i]);
        }
        double l=1;
        while(r-l>1e-5)
        {
            double mid=(r+l)/2;
            if(check(mid)) l=mid;
            else r=mid;
        }
        System.out.println((int)(r*1000));
    }
}

学到的知识

string 字典序最小
sort(s.begin(),s.end())
最大
sort(s.begin(),s.end(),greater<int>())

sort(s.begin(),s.end()); 
reverse(s.begin(),s.end());

贪心＋二分

贪心：我们该字符串最前面的位置，可以将该字符串变为最小，插入字符串最大的排列中。

证明：假如由有最优解，两种情况，

  • 有字符串可以排到它后面，但每个字符串都已经字典序最大了，所以不行
  • 我们当前字符串可以变换更小，但我们已经最小了~

反之，我们的得到最后的位置，就是将当前字符串变最大，插入最小的排列中。

二分：

在得到最前位置的时候，用当前字符串的字典序最大，去在最小的序列中找 第一个>=的字符串
在得到最后位置的时候，用当前字符串的字典序最小，去在最大的序列中找 最后一个<=的字符串

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first 
#define y second
using namespace std;
typedef pair<string,string> PSS;
const int N=50010;
string Smin[N],Smax[N];
PSS alls[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        string t;
        cin >> t;
        sort(t.begin(),t.end());
        Smin[i]=t;
        reverse(t.begin(),t.end());
        Smax[i]=t;
        alls[i]={Smin[i],Smax[i]};
    }
    sort(Smin+1,Smin+n+1);
    sort(Smax+1,Smax+n+1);
    for(int i=1;i<=n;i++)
    {
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(Smax[mid]>=alls[i].x)r=mid;
            else l=mid+1;
        }
        cout << l <<' ' ;
        l=1,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(Smin[mid]<=alls[i].y)l=mid;
            else r=mid-1;
        }
        cout << r << endl;        
    }
    return 0;
}

题目大意：

​ 给我们\(n\)​个数字，且对于每个\(i(1<=i<n)\)​ 我们\(A_i和A_{i+1}\)​​中间要至少选一个，求这样选取的中位数和平均值最大是多少?

解法：
玄学二分

前置： dp求这样选整个序列的最大值

    $ f[i][j] $ ： 表示 从前 $i$个物品选且第$i$个物品的状态是 $j$ 时，选取的最大值 （ $j$有两种取值，`0`代表不取，`1`代表取 ）

​ 转移方程 ： \(f[i][1] = max(f[i-1][0],f[i-1][1])+b[i]\)

​ \(f[i][0]=f[i-1][1]\) 当我们这个物品不选时，上个物品必须选，如果不选则不满足至少选一个。（当然我们会发现我们只会用到上一维度可以优化）用 \(f\)代表\(f[i][1]\) 用 \(g\) 表示 \(f[i][0]\) ，如果我们更新时我们这两个值存储的是上一层的，我们更新这一维度的。

int t = max(f,g) + b[i];
g = f;
f = t;

  • 当我们求平均数时，采用的是浮点数二分，当我们枚举的数大时，我们这样选取的最大值是\(<0\) 的，当小时 \(>0\) , 当等于答案时是\(=0\)，所以当 \(>=0\)​时我们要变换左边界。

  • 当我们求中位数时，是要将我们的这个数尽可能的选多点，尽可能的让他靠近中间的位置，奇数时我们中位数的位置在(n+1)/2，也就是我们不包括中位数左右两边的数一样多，偶数的时候在n/2也就是左半边最后一个数，两种情况汇总也就是说我们>=x的数严格多于小于x的数，我们将 >= x的数设为 \(1\)​ ，<x的数设为\(-1\)​，这样当我们选取的最大值>0我们这个数满足，当<0时不满足，=0时说明 x在中间偏右一个位置。

    代码

    #include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
using namespace std;

const int N = 100010;
vector<int> a(N);
int n;

template<typename T> T check(T x,T b[])
{
   T f = 0, g=0;
   for(int i=0;i<n;i++)
   {
       T t = max(f,g) + b[i];
       g = f;
        f = t;
   }
    return max(f,g);
}



int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    cin >>n;
    for(int i=0;i<n;i++) cin >> a[i];
    double l = 1 ,r = 1e9+10;
    while(r-l>1e-5)
    {
        double b[n];
        double mid = (l + r) / 2;
        for(int i=0;i<n;i++) b[i] = a[i] - mid;
        if(check(mid,b)>=0) l=mid;
        else  r=mid;
    }
    int l1=1,r1=1e9;
    int b[n];
    while(l1<r1)
    {
        int mid = l1 + r1 + 1>>1;
        
        for(int i=0;i<n;i++) b[i] = a[i]>= mid ? 1 : -1;

        if(check(mid,b)>0) l1 = mid; 
        else r1 = mid - 1;

    }
    printf("%.2lf\n%d",l,l1);
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

​

上一篇：day10字符串和函数基础


下一篇：static作用在单例模式下