插入排序(CSP-J 2021 T2)

2022/7/29 23:23:16

本文主要是介绍插入排序(CSP-J 2021 T2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

题目:(由于题干过长直接上链接:P7910 [CSP-J 2021] 插入排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) 不是打广告

又有一个新思路:

我们可以再开一个b数组用来记录第i个数排序后的位置并在更改数据(操作一)后维护b数组,使b数组依然适用。

 

 同时还要开一个struct(用于a数组)记录一个id(输入顺序)一个va(输入内容)。

因为要初始化(根据输入数据)b数组要把a sort一遍因为是sort结构体就要自定义cmp(重点来了!)因为我们要模拟稳定的排序所以自定义cmp中除了正常操作还有一点,如果a的输入顺序比b大也要交换。.

初始化b数组遍历一遍a数组将b[a[i].id]设为i(意为第a[i].id个数在排序后在i的位置)

 

 

 接下来就是维护b数组的问题。

如果替换的数值比原来大就要向左边做一次冒泡,把它放到合适的位置。(如果它不交换了就break掉,能节省不少时间)如果替换的数值比原来的大就想做做冒泡……(同理)

在第一种操作结束之前,我们还要再初始化一遍b数组(初始化b数组遍历一遍a数组将b[a[i].id]设为i)。

如果是第二种操作,十分简单输入x,输出b[x]即可(别问我为什么,看了那么多还不明白就重看吧!)。

代码:

#include<bits/stdc++.h>
using namespace std;
struct s{
    int id;
    int va;
}a[8010];
int n,q,b[8010]={0};
int cmp(const s &a,const s &b)
{
    if(a.va!=b.va) return a.va<b.va;
    else return a.id<b.id;
}
int main()
{
#ifdef LOCAL
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].va;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        b[a[i].id]=i;
    }
    while(q--)
    {
        int t;
        scanf("%d",&t);
        if(t==1)
        {
            int x,v;
            scanf("%d%d",&x,&v);
            if(a[b[x]].va<v)
            {
                a[b[x]].va=v;
                for(int i=b[x];i<n;i++)
                {
                    if(a[i].va>a[i+1].va||(a[i].va==a[i+1].va&&a[i].id>a[i+1].id)) swap(a[i],a[i+1]);
                    else break;
                }
            }
            else
            {
                a[b[x]].va=v;
                for(int i=b[x]-1;i>=1;i--)
                {
                    if(a[i].va>a[i+1].va||(a[i].va==a[i+1].va&&a[i].id>a[i+1].id)) swap(a[i],a[i+1]);
                    else break;
                }
            }
            for(int i=1;i<=n;i++)
            {
                b[a[i].id]=i;
            }
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",b[x]);
        }
    }
    return 0; 
}

 

最后,祝大家暑假快乐!

 



这篇关于插入排序(CSP-J 2021 T2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程