头像

Pinguier

青岛大学




离线:19小时前


最近来访(4)
用户头像
sealt
用户头像
嗨嗨害
用户头像
dabai

活动打卡代码 AcWing 788. 逆序对的数量

#include<iostream>

using namespace std;
const int N =100010;
//这里因为逆序对的最大个数超过了int的存储范围 所以使用long long类型
typedef long long LL;
int n;
int q[N],temp[N];
LL merge_sort(int q[],int l,int r){
    if(l>=r) return 0;
    int mid = l + r >>1;
    LL res = merge_sort(q,l,mid) + merge_sort(q,mid+1,r);
    //归并算法
    int k =0,i =l,j=mid+1;
    while(i<=mid && j<=r){
        if(q[i]<=q[j]) temp[k++] = q[i++];
        else{
            temp[k++] = q[j++];
            res += mid-i+1;
        }
    }
    //扫尾
    while(i<=mid) temp[k++] = q[i++];
    while(j<=r) temp[k++] = q[j++];
    //排序赋值
    for(int i =l,j =0;i<=r;i++,j++) q[i]=temp[j];

    return res;
}

int main(){
    scanf("%d",&n);
    for(int i = 0; i<n;i++) scanf("%d",&q[i]);
    cout<<merge_sort(q,0,n-1)<<endl;


    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include<iostream>

using namespace std;
int main(){
    double x;
    cin>>x;
    double l=-1000,r=1000;
    //题目要求保留六位小数 通常这里判断循环取小数点后八位
    while(r-l>=1e-8){
    //浮点数二分很简单 只需要考虑mid值与答案之间的关系 使区间边界直接移动到mid即可
        double mid = (l+r)/2;
        if(mid*mid*mid<=x) l=mid;
        else r=mid;
    }
    printf("%.6lf",l);
    return 0;
}






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

//快速排序后再输出 时间复杂度高
##include<iostream>
//快速选择算法 时间复杂度为O(n)
using namespace std;
const int N=100010;
int n,k;
int q[N];
int quick_sort(int l ,int r ,int k){
    if(l==r) return q[l];
    int x = q[l+r>>1];
    int i =l-1 , j = r + 1;
    while(i<j){
    do(i++);while(q[i]<x);
    do(j--);while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
    }
    int stl = j-l+1;
    if(k<=stl) return quick_sort(l,j,k);
     return quick_sort(j+1,r,k-stl);

}
int main(){
    cin>>n>>k;
    for(int i =0;i<n;i++) cin>>q[i];
    cout<<quick_sort(0,n-1,k)<<endl;


    return 0;
}




活动打卡代码 AcWing 789. 数的范围

#include<iostream>

using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i =0 ;i<n;i++) scanf("%d",&q[i]);
    while(m--){
        int x;
        scanf("%d",&x);
        //二分模板 先假定mid为l+r>>1 如果l=mid 则加1  如果r=mid 则不加1
        int l=0,r=n-1;
        while(l<r){
            int mid = l + r>>1;
            //判断最左边的下标 则判断中点的值是否满足>=x 如果满足 则答案x一定在中点值的左边 也就是在区间 l-mid中 此时令r=mid
            if(q[mid]>=x) r=mid;
            else l=mid +1;
        }
        if(q[l]!=x){
            cout<<"-1 -1"<<endl;
        }
        else{
            cout<<l<<' ';
            int l=0,r=n-1;
            while(l<r){
            //判断最右边的下标 则判断中点的值是否满足<=x 如果满足 则答案x一定在中点值的右边 也就是在区间mid-r中 此时令l=mid

                 int mid = l+r+1>>1;
                 if(q[mid]<=x) l =mid;
                 else r=mid-1;
            }
            cout<<l<<endl;

        }
    }
    return 0;
}


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

#include<iostream>
using namespace std;
const int N=1000010;
int n;
int q[N],temp[N];
void merge_sort(int q[], int l, int r){
    if(l>=r) return;
    int mid = l + r >>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r){
        if(q[i]<q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++] = q[j++];
    for(int 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]);
    }
}




题目描述

归并排序模板

样例



C++ 代码

#include<iostream>
using namespace std;
const int N=1000010;
int n;
int q[N],temp[N];
void merge_sort(int q[],int l, int r){
    if(l>=r) return;
    int mid = l + r >>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid &&j<=r){
        if(q[i]<q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++] = q[j++];
    for(int 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 785. 快速排序

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];
//如果递归取j 则x不能取q[r] 同理 如果递归区间取i 则x不能取q[l] 否则会有边界问题
void quick_sort(int q[],int l,int r)
{
if(l>=r) return ;
//确定左边界为中间值 使得数组左侧数据全部为小于x的值 右侧数据为大于x的值
int x=q[l];
i=l-1;
j=r+1;
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
//交换函数
if(i<j){
    int t =q[i];
    q[i]=q[j];
    q[j]=q[i];
}
}
//递归继续对左右两侧的数组进行排序
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++){
        printf("%d",q[i]);
    }
    return 0;
}


新鲜事 原文

AcWing《每日一题·夏季》拼团优惠!https://www.acwing.com/activity/content/introduction/43/group_buy/90249/