头像

DaHUA




离线:3天前



DaHUA
7天前

题目描述

给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。
输入格式
第一行包含整数n和q,表示数组长度和询问个数。
第二行包含n个整数(均在1~10000范围内),表示完整数组。
接下来q行,每行包含一个整数k,表示一个询问元素。
输出格式
共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回“-1 -1”。
数据范围
1≤n≤100000
1≤n≤100000

1≤q≤10000
1≤q≤10000

1≤k≤10000
1≤k≤10000

样例

输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1

优化二分查找跳过重复元素

此题采用正常的二分查找会超时,但我们可以注意到,此题有很多重复的数字例如(111223333)
我们二分查找时左边查找到第一个1的时候就可以跳过其余的1
可以通过一个数组来实现记录重复数字的个数,在二分查找时可以直接跳过

java代码

package 蓝桥;

import java.util.Scanner;
/******
 * 
 * @author genji
 * 此题采用正常的二分查找会超时,但我们可以注意到,此题有很多重复的数字例如(111223333)
 * 我们二分查找时左边查找到第一个1的时候就可以跳过其余的1
 * 可以通过一个数组来实现记录重复数字的个数,在二分查找时可以直接跳过
 */
public class 数的范围_789 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt(),m=scanner.nextInt();
        int[] a=new int[n];
        int[] b=new int[n];//b中存放重复数字的数量,因为下面采用二分查找所以有前后两个标志
        //例如a 中的数为1,1,1,1,1,2,2,2,2,3,3,4,4,4,4,5
        //则b中的数为      5,0,0,0,5,4,0,0,4,2,2,4,0,0,4,1
        //使其在查找时跳过重复的数字
        int c=0,i;
        for (i = 0; i < n; i++) {
            a[i]=scanner.nextInt();
            if (i==0||a[i]==a[i-1]) {
                c++;                //如果是第一个数或者和前面数字相同的数则记录相同数字的个数
            }
            else if (a[i]!=a[i-1]) {
                b[i-1]=c;
                b[i-c]=c;           //将相同数字个数赋到b数组相同下标的头和尾
                c=1;
            }
        }
        b[i-1]=c;
        b[i-c]=c;
        for (i = 0; i < b.length; i++) {
            System.out.println(b[i]);
        }
        while (m-->0) {
            int l=0,r=n-1;
            int q=scanner.nextInt();
            while (l<r) {

                if (a[l]!=q) {

                    l+=b[l];//   跳过重复的数字
                }
                if (a[r]!=q) {
                    r-=b[r];//   跳过重复的数字
                }
                if (a[r]==q&&a[l]==q) {

                    System.out.println(l+" "+r);
                    break;
                }
            }
            if(a[l]!=q&&a[r]!=q)
            {
                System.out.println(-1+" "+-1);
            }

        }
    }
}




活动打卡代码 AcWing 787. 归并排序

DaHUA
26天前
#include<stdio.h>

const int N=100005;
int q[N],n;
void  merge_sort(int q[],int l,int r){
    if(l>=r)return;
    int k=(l+r)/2;
    merge_sort(q,l,k);
    merge_sort(q,k+1,r);

    int i=l,j=k+1;int h=0;int temp[r-l+1];//*
    while(i<=k&&j<=r)
        if(q[i]<=q[j])temp[h++]=q[i++];
        else temp[h++]=q[j++];

    while(i<=k)temp[h++]=q[i++];
    while(j<=r)temp[h++]=q[j++];

    for(i=l,j=0;i<=r;i++,j++)q[i]=temp[j]; //*
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++){
        printf("%d ",q[i]);
    }
}



活动打卡代码 AcWing 786. 第k个数

DaHUA
27天前
#include<iostream>
using namespace std;
const int N=1e5+1;
int a[N];
int k,n;

void quick_sort(int a[],int l,int r){

    if(l==r)return;
    int tmp=a[l+r>>1];
    int i=l-1;
    int j=r+1;
    while(i<j){
        do i++;while(a[i]<tmp);
        do j--;while(a[j]>tmp);
        if(i<j)swap(a[i],a[j]);
    }
   quick_sort(a,l,j);
   quick_sort(a,j+1,r);

}

int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quick_sort(a,0,n-1);
    printf("%d",a[k-1]);

}



活动打卡代码 AcWing 785. 快速排序

DaHUA
1个月前
思想:分治,递归
快速排序要注意很多的边界问题

1.在数组中选一个参考数x,虽说可以任意选,但最好是x=q[(i+r)/2] 
2.将数组依照x,分为左边 <x ,右边 >x
3.将左边区域和右边区域进行快排
#include<iostream>
using namespace std;
const int MAXSIZE=1e6+10;//如果是1e9会报错
int n,a[MAXSIZE];
void quick_sort(int q[], int l, int r) {
    int i,j,x;
    if(l>=r)return;//破除条件
    i=l-1;// i,j初始条件,方便下面分区
    j=r+1;
    x=q[(l+r)/2];
    while(i<j){
        do i++;while(q[i]<x);//不能是<=
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);//如果是j,x选值不能是q[l];如果是i,x的选值不能是q[r];
    quick_sort(q,j+1,r);
}


int main(){
     int i;
     scanf("%d",&n);
     for(i=0;i<n;i++){
         scanf("%d",&a[i]);
     }
     quick_sort(a,0,n-1);
     for(i=0;i<n;i++){
         printf("%d ",a[i]);
     }
     return 0;
}



DaHUA
8个月前
#include<iostream>
using namespace std;
const int N=1010;
int n;
int f[N],a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
     {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            f[i]=max(f[i],f[j]+1);
         }
     }
     int res=0; 
     for(int i=1;i<=n;i++)
     res=max(res,f[i]);
    cout<<res;
    return 0;
} 


活动打卡代码 AcWing 898. 数字三角形

DaHUA
8个月前
//从上往下推的情况
#include<iostream>
using namespace std;
 const int N=1010;

 int n;
 int dp[N][N];
 int a[N][N];
 int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        cin>>a[i][j];
     }
      for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)
            dp[i][j]=-1e9;
        //因数据有负数,将数据和边界两侧扩展初始化为负无穷,这样比较不会出错


    dp[1][1] = a[1][1];
     for(int i=2;i<=n;i++)
     {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);//走[i,j]之前是前i-1层j-1列还是j列
          }
      }
      int res=-1e9;//保证比 走到第n行相加的数小 不出错
      for(int i=1;i<=n;i++)
        res=max(dp[n][i],res);//第n行中和选最大的
        cout<<res<<endl;
     return 0;
 }

 //从上往下
 #include<iostream>
using namespace std;
const int N=1010;
int dp[N][N],a[N][N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        cin>>a[i][j];
    }

    for(int i=n;i>=1;i--)//因为初始值都为0 n+1层所以不影响结果
    {
        for(int j=1;j<=i;j++)
         dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    }
    cout<<dp[1][1];
    return 0;
}



活动打卡代码 AcWing 898. 数字三角形

DaHUA
8个月前

```

include[HTML_REMOVED]

using namespace std;
const int N=1100;
const int INF=1e9;
int n;
int dp[N][N];
int a[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i)
{
for(int j=1;j<=i+1;j
)
cin>>a[i][j];
}
for(int i=0;i<=n;i)
for(int j=0;j<=i;j
)
dp[i][j]=-INF;

 //dp[1][1] = a[1][1];
 for(int i=1;i<=n;i++)
 {
    for(int j=1;j<=i;j++)
    {
        dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
      }
  }
  int res=-INF;
  for(int i=1;i<=n;i++)
    res=max(dp[n][i],res);
    cout<<res;
 return 0;

}

```



活动打卡代码 AcWing 9. 分组背包问题

DaHUA
8个月前
#include<iostream>
using namespace std;
 const int N=500;
 int n,m,v[N][N],w[N][N],s[N];
 int f[N];
 int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {

        cin>>s[i];
        for(int j=1;j<=s[i];j++)cin>>v[i][j]>>w[i][j];//输入每一组的每一件物品的体积和价值
     }
     for(int i=1;i<=n;i++)//从前i个组里选
     {
        for(int j=m;j>=1;j--)//总体积不超过m
        {
            for(int k=1;k<=s[i];k++)
            if(v[i][k]<=j)//选的每一组里的每一件物品如果总体积不超过j
             f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
         }
     }
     cout<<f[m];
     return 0;
 }


活动打卡代码 AcWing 5. 多重背包问题 II

DaHUA
8个月前
//多重背包 
#include<iostream>
#include<algorithm>
using namespace std;
const int N=12000;//背包容量:1000*log2000
int n,m,v[N],w[N],f[N];
int v1,w1,s;
int op=0;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v1>>w1>>s;
        int k=1;
        while(k<=s)//二进制拆分
        {
            v[++op]=k*v1;
            w[op]=k*w1;
            s-=k;
            k*=2;
        }
        if(s)
        {
            v[++op]=v1*s;
            w[op]=w1*s;
        }
    }

    for(int i=1;i<=op;i++)
    {
        for(int j=m;j>=v[i];j--)//套用01背包
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
    //总物品数:NlogS
   //时间复杂度:VNlogS
}


活动打卡代码 AcWing 4. 多重背包问题

DaHUA
8个月前
//第一种
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int s[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)//对完全背包做修改,加上判断最多选到s

                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);


        }
    }
    cout<<f[n][m];
    return 0;
}

//第二种

#include<iostream>
#include<algorithm>
const int N=150;
int n,m,v[N],w[N],s[N]f[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++){
        for(int k=0;k<=s[i];k++)//把si件物品当成si种
        {
            for(int j=m;j<=v[i];j++)
            {
                f[j]=max(f[j],f[j-v[i]]*k+w[i]*k);//对每一件物品i做si遍01背包
            }
        }
    }
}