基础算法acwing刷题指南6

目录：

786. 第k个数

787. 归并排序

789. 数的范围

786. 第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择class="superseo">算法求出数列从小到大排序后的第 k 个数

输入格式

第一行包含两个整数 n和 k。

第二行包含 n 个整数（所有整数均在10^9范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

输入样例：

5 3
2 4 1 5 3

输出样例：

3

学习了STL中的sort就应该实践一下

#include

using namespace std;

const int N = 1e5 + 10;

int n, m;
int q[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> q[i];

    sort(q, q + n);
    cout << q[m - 1] << endl;

    return 0;
}

快排：

#include
using namespace std;
const int N = 1e5 + 10;
int n, m;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int x = q[l + r >> 1], 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]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}//这种方法好记很多

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> q[i];

    quick_sort(q, 0, n - 1);

    cout << q[m - 1] << endl;

    return 0;
}

787. 归并排序

给定你一个长度为 n 的整数数列。

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

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

输入格式

输入共两行，第一行包含整数 n。

第二行包含n 个整数（所有整数均在1~10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

#include
using namespace std;
const int N = 100500;
int a[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,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}

//板子，记下就好
int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i++)cin>>a[i];
    merge_sort(a,0,n-1);
    
    for(int i = 0;i < n;i++)cout<     return 0;
}

求解逆序对问题,实际上有三种算法可以处理,分别是冒泡算法,归并排序,以及树状数组求解.

这里显然我们可以用性价比最高,代码最好写,效率特高的归并排序算法。

我们要注意一点,就是当我们发现填充第二个数组中的数,加入备用数组的使用,都要统计mid−i+1,因为此时此刻,我们第一个数组中剩余的所有数,都会和它构成逆序对。

去网站上去看数据范围，容易爆，于是我们开long long

#include

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int a[N], tmp[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]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}

789. 数的范围

本题是练习二分很好的一道题目，二分程序虽然简单，但是如果写之前不考虑好想要查找的是什么，十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已。用二分去查找元素要求数组的有序性或者拥有类似于有序的性质，对本题而言，一个包含重复元素的有序序列，要求输出某元素出现的起始位置和终止位置，翻译一下就是：在数组中查找某元素，找不到就输出-1，找到了就输出不小于该元素的最小位置和不大于该元素的最大位置。所以，需要写两个二分，一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数。查找不小于x的第一个位置

#include
using namespace std;

const int N = 100001;
int n,m;
int q[N];
int main()
{
    cin>>n>>m;
    for(int i = 0;i < n;i++)cin>>q[i];
    
    while(m--)
    {
        int x;
        cin>>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"<         else 
        {
            cout<             
            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<         }
    }
    return 0;
}