逆序对的数量

这题一看就可以用暴力做，但是数据量要再大一点，就会TLE。

于是，我们就要调整一下思路。

解释：在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来，归并排序分治我们求的是从小到大的顺序，我们所求的逆序对恰好是逆序数量，与归并排序不谋而合。

这种方法当然可以，这种方法有一个名字：二路归并

这种算法跟二分有点像，又跟归并排序的原理有点像，所以，我们可以用 归并排序的模版做，根据规则调整就行。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

于是，我们可以写出代码了：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int n;

int q[N];

LL merge_sort(int l,int r)
{
    if (l>=r) return 0;

    int mid=l+r>>1;

    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);

    int k=0;

    //归并的过程
    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++];
            res+=mid-i+1;
        }

    //扫尾
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];

    //物归原主
    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

    return res;
}

int main()
{
    cin>>n;

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

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

    return 0;
}

二分之整数范围

在正式讲解之前，我们要知道二分是干啥用的

二分，其实就是一种查找算法，一般顺序查找的时间复杂度是o(n)，而二分是提升时间复杂度的，可以将o(n)提升到o(logn)级别。一般二分查找分为两类：整数二分和实数二分。整数二分非常容易错，建议多研究。实数二分比较简单，一般大家琢磨琢磨就会了。

这题就是一个整数二分。

首先，我们知道，二分有两个模版：

int search_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int search_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid + 1;
    }
    return l;
}

我们要根据不同的题目调用不同的模版

两个模版区别具体见 among大佬的闫总“二分查找算法”两个模板本质差别

那么，此题需要用什么模版呢?

仔细研究发现，这题要用第一个模版。

那么，把模版套入代码中就行了。

代码如下：

#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    while (q--) {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] < x)  l = mid + 1;
            else    r = mid;
        }
        if (a[l] != x) {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;
        while (l1 + 1 < r1) {
            int mid = l1 + r1 >> 1;
            if (a[mid] <= x)  l1 = mid;
            else    r1 = mid;
        }
        printf("%d %d\n", l, l1);
    }
    return 0;
}

归并排序正解

首先，我们要了解归并排序是怎么实现的。

应该还是_分治_思想

那它怎么实现呢？

1.确定分界点

2.递归排序left、right

3.归并——合二为一 这也是步骤最最关键的部分

于是，我们就可以写出代码了：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r);
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;
}
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];
    return;
}

调整一下快速排序的模版即可

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, q, a[100010];
void quick_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    int i = l - 1, j = r + 1, x = a[mid];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quick_sort(1, n);
    cout << a[q];
    return 0;
}

在此之前宣布：算法基础课第二遍已经开始

以后，我再也不会氵题解了！我再也不会摆烂了！梦想重新启航！

这里是我的算法基础课笔记

我不光是给自己看，也是给大家看！

从此之后，我再也不是一位只会摆烂的蒟蒻了！

持续更新中ing~~~

我不求赞！只求和大家一起进步！

算法基础课笔记

1.基础算法

1.1 快速排序

1.2 第k个数

1.3 归并排序

1.4 逆序对的数量

1.5 数的范围

2.数据结构

3.搜索与图论

4.数学知识

5.dp

6.贪心

快速排序正解

首先我们都知道快速排序可以用系统函数解。

于是就产生了如下的代码：

#include <iostream>
#include <algorithm>//注意sort在algorithm头文件里

using namespace std;

const int N = 100010;//定义数组长度

int n;
int a[N];

int main(){
    cin >> n;//输入，当然scanf也没毛病
    for (int i = 0; i < n; i ++ ) cin >> a[i];//循环输入，当然从1开始也没毛病
    sort(a, a + n);//调用系统函数sort
    for (int i = 0; i < n; i ++ ) cout << a[i] << ' ';//循环输出，当然printf也没毛病
    return 0;
}

这种方法虽然好，但是无法通过面试，于是，我们就要手写sort函数

怎么写呢？？？

我们就可以用 分治 的思想：

1.确定分界点：q[l] q[(l + r) / 2] q[r] 随机

2.调整范围：我们需要找到一个分界点x，使得它左边的数都小于等于它，右边的数都大于等于它

3.递归处理左右两段：

(1).遍历q[l~r],如果q[i] <= x,就将x插到左边去,如果q[i] >= x，就将x插到右边去

(2).还原

于是，我们就产生了这样的代码：

#include <iostream>

using namespace std;

const int N = 100010;

int q[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()
{
    int n;
    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;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1010;
const LL INF = 1e18;

int n, m;
int w[N][N];
LL f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);

    memset(f, -0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 1; i <= m; i ++ )
    {
        LL s = -INF;
        for (int j = 1; j <= n; j ++ )
        {
            s = max(s, f[j][i - 1]) + w[j][i];
            f[j][i] = max(f[j][i], s);
        }
        s = -INF;
        for (int j = n; j; j -- )
        {
            s = max(s, f[j][i - 1]) + w[j][i];
            f[j][i] = max(f[j][i], s);
        }
    }

    printf("%lld\n", f[n][m]);
    return 0;
}