四、排序+查找

排序

贪心

排序不等式

课程链接： https://www.acwing.com/video/339/
自己的笔记 ： https://www.acwing.com/activity/content/code/content/6700247/

赛前练习：排队打水

#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;
int n;
int q[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];
    sort(q,q+n);
    long long s=0;
    for(int i=1;i<=n;i++)
    {
        s+=q[i-1]*(n-i);
    }
    cout<<s;
    return 0;
}

区间问题

1、区间选点

课程链接 ： https://www.acwing.com/activity/content/problem/content/1111/
自己的笔记 ： https://www.acwing.com/activity/content/code/content/6179496/

赛前练习：

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;
int n;

struct Range
{
    int l,r;
    bool operator < (const Range &W)const
    {
        return r<W.r;
    }
}range[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    int ed=-2e9,res=0;
    sort(range,range+n);
    for(int i;i<n;i++)
    {
        if(range[i].l>ed)
        {
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
    return 0;
}

快速排序

课程链接 ： https://www.acwing.com/activity/content/problem/content/819/

赛前练习：

#include<iostream>
using namespace std;
const int N=1e6*10;

int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if (l>=r) return;//判边界
    int x=q[(l+r)/2],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()
{
    scanf("%d",&n);//scanf一般比cin快
    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;
}

重点：
1、主要思想：分治；
2、主要步骤：
-确定分界点：左、中、右、随机值
-根据分界点调整区间，使得第一个区间的所有-数都小于等于x，第二个区间所有的数大于等于x
-递归处理左右两部分
3、要注意do while和while的区别，此处如果i=l,j=r然后使用while，可能会导致程序卡死，因为while是先判断后执行大括号的内容，如果不满足判断条件，例如当q[i]和q[j]数值军等于分界点时，无论交换多少次都是不满足while的判断条件的，因此会卡住；反之，如果用do while，就不会出现这种情况
4、while判断条件不能取等号

归并排序

课程链接 ： https://www.acwing.com/video/229/
自己的笔记 ： https://www.acwing.com/activity/content/code/content/5901450/

#include<iostream>

using namespace std;
const int N=100010;

int n;
int q[N];
int temp[N];

void merge_sort(int l,int r,int q[])
{
    if(l>=r) return;
    int mid = (l+r)/2;

    merge_sort(l,mid,q),merge_sort(mid+1,r,q);
    int i=l,j=mid+1,k=0;
    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++) cin>>q[i];
    merge_sort(0,n-1,q);
    for(int i=0;i<n;i++) cout<<q[i]<<' ';
    return 0;
}

重点：
1、主要思想也是分治，但和快速排序有区别；
2、找到分界点后，先递归左右两边，再归并

查找

二分

哈希