头像

我真的想笑




离线:53分钟前


最近来访(1)
用户头像
杰克伦敦写的是野性的呼唤


题目描述
给定一个按照升序排列的长度为$n$的整数数组,以及$q$个查询。

对于每个查询,返回一个元素$k$的起始位置和终止位置(位置从$0$开始计数)。

如果数组中不存在该元素,则返回-1 -1。

输入格式
第一行包含整数$n$和$q$,表示数组长度和询问个数。

第二行包含$n$个整数(均在$1\sim10000$ 范围内),表示完整数组。

接下来$q$行,每行包含一个整数$k$,表示一个询问元素。

输出格式
共$q$行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回 -1 -1。

数据范围
$1\le n\le100000$
$1\le q\le10000$
$1\le k\le10000$

输入样例

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

解题思路
本题可以利用二分查找的两个模版来做,正好第一个模版可以求出起始位置,因为第一个模版是从左往右找;第二个模版可以求出终止位置,因为第二个模版是从右往左找。

#include<iostream>
using namespace std;
const int N=100010;
int n,m,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);
        int l=0,r=n-1;
        //第一个模版,从中往右寻找
        while(l<r){
            int mid=l+r>>1;
            if (q[mid]>=x){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        if (q[l]!=x){
            cout<<"-1 -1"<<endl;
        }
        else{
            cout<<r<<' ';
            int l=0,r=n-1;
            //第二个模版,从右往左寻找
            while(l<r){
                int mid=l+r+1>>1;//记得加一
                if (q[mid]<=x){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            cout<<r<<endl;
        }
    }
    return 0;
}



题目描述
给定一个长度为$n$的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第$i$个和第$j$个元素,如果$i<j$,且$a[i]$大于$a[j]$则其为一个逆序对;否则不是

输入格式
输入共两行,第一行包含整数$n$,表示数列的长度。

第二行包含$n$个整数(所有整数均在$1\sim 10^9$范围内),表示整个数列。

输出格式
输出一个整数,表示逆序对的数量。

数据范围
$1\le n \le 10000$

输入样例

6
2 3 4 5 6 1

输出样例

5

解题思路
本题可以利用归并排序的思想来解题,当我们进行归并排序时,最后一步是将两部分已经排好序的进行归一处理,也就是说这时候左边的一段的位置都在右边一段的前面,如果要将右边的元素插入新的序列时,则左边的一段中剩下的元素都可以与插入的元素组成逆序对,因为其位置都在插入的元素前面,但是其都比插入的元素大。

#include<iostream>
using namespace std;
typedef long long  LL;
const int N=1e+5+10; 
int q[N],tem[N];

LL merge_sort(int q[],int l,int r){
    if (l >= r){
        return 0;
    }
    int mid=l + r >> 1;
    LL num=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]){
            tem[k++]=q[i++];
        }
        else{
        //逆序对的数量为第一个区间中剩下的元素个数,也就是i-mid之间的元素个数
            num += mid-i+1; 
            tem[k++]=q[j++];
        }
    }
    while (i<=mid){
        tem[k++]=q[i++];
    }
    while (j<=r){
        tem[k++]=q[j++];
    }
    for (int i=l,k=0;i<=r;i++,k++){
        q[i]=tem[k];
    }
    return num;
}

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



题目描述
给定你一个长度为$n$的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行,第一行包含整数 $n$。

第二行包含$n$个整数(所有整数均在$1\sim 10^9$范围内),表示整个数列。

输出格式
输出共一行,包含$n$个整数,表示排好序的数列。

数据范围
$1\le n \le 10000$

输入样例

5
3 1 2 4 5

输出样例

1 2 3 4 5

解题思路
本题较为基础,直接套用模版即可。

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



题目描述
给定一个长度为$n$的整数数列,以及一个整数$k$,请用快速选择算法求出数列从小到大排序后的第$k$个数。

输入格式
第一行包含两个整数$n$和$k$。

第二行包含$n$个整数(所有整数均在$1\sim10^9$范围内),表示整数数列。

输出格式
输出一个整数,表示数列的第$k$个数。

数据范围
$1\le n\le100000$
$1\le k\le n$

输入样例

5 3
2 4 1 5 3

输出样例

3

解题思路
正常快速排序,然后输出第k个数即可。因为数列下标是从0开始,所以输出的是q[k-1]

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;

void quick_sort(int q[], int l, int r){
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + 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]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1,r);
}

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



题目描述
给定你一个长度为$n$的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行,第一行包含整数 $n$。

第二行包含$n$个整数(所有整数均在$1\sim 10^9$范围内),表示整个数列。

输出格式
输出共一行,包含$n$个整数,表示排好序的数列。

数据范围
$1\le n \le 10000$

输入样例

5
3 1 2 4 5

输出样例

1 2 3 4 5

解题思路
本题较为基础,直接套用模版即可

代码实现:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;

int q[N],n;

//快排模版
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + 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]);
    }
    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;
}