首页 > 其他分享 >[Luogu] P7910 [CSP-J 2021] 插入排序

[Luogu] P7910 [CSP-J 2021] 插入排序

时间:2023-11-24 20:37:43浏览次数:55  
标签:node int Luogu P7910 插入排序 maxn data CSP

[CSP-J 2021] 插入排序 - 洛谷

昨天下午爆肝一下午都没整出来(悲

是我太菜了

思路

第一种想法,暴力

即,每次修改操作后重新维护整个数组,时间复杂度\(O(Qn^2)\),能拿52pts

但是,想要拿满分,很简单,只需要把排序的双层循环\(n^2\)变为\(n\)即可

因为冒泡是对每个点都进行枚举,但是需要修改的只有一个点的位置,因此只需要按一个点进行枚举即可

代码

代码实现如下,时间复杂度\(O(nQ)\)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n,q;
int f[maxn];//f[i]表示原序列中的第i个,在新的序列里的位置
struct node
{
    int data,id;
}a[maxn];
bool cmp(node x,node y)
{
    if(x.data!=y.data) return x.data<y.data;
    else return x.id<y.id;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].data;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        f[a[i].id]=i;
    }
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)//第一种操作
        {
            int x,y;
            cin>>x>>y;
            a[f[x]].data=y;
            for(int i=n;i>=2;i--)
            {
                if(cmp(a[i],a[i-1]))
                {
                    // cout<<"change small"<<endl;
                    swap(a[i-1],a[i]);
                }
            }
            for(int i=2;i<=n;i++)
            {
                // cout<<"change bigger"<<endl;
                if(cmp(a[i],a[i-1]))
                {
                    swap(a[i-1],a[i]);
                }
            }
            for(int i=1;i<=n;i++)
            {
                f[a[i].id]=i;
            }
            // for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;
        }else//第二种操作
        {
            int x;
            cin>>x;
            cout<<f[x]<<endl;
        }
    }
}

标签:node,int,Luogu,P7910,插入排序,maxn,data,CSP
From: https://www.cnblogs.com/lyk2010/p/17854696.html

相关文章

  • [Luogu] P7911 [CSP-J 2021] 网络连接
    [CSP-J2021]网络连接-洛谷距离CSP2023还有\(**3**\)天题意及思路恶臭大模拟,按照题意模拟即可。有几个代码上的难点:当定义了一个scanf或者sscanf并且有一定的输入规则,那么如果读取到的字符串不符合定义的规则,那读入了几个变量就返回几个变量例如,如下代码定义了一个读......
  • [Luogu] P1164 小A点菜
    题目传送门一道动态规划,\(dp_{i, j}\)表示用前\(i\)个菜品花光\(j\)元的方法总数那么可以推出状态转移方程:\(if(j>a_i)\spacedp_{i,j}=dp_{i-1,j}+dp_{i-1,j-a_{i}}\)如果j比ai大,那么方案数就是不买\(dp_{i − 1, j}\)+买\(dp_{i − 1, j − a_i}\),其中如果买,那么......
  • [Luogu] P1114 “非常男女”计划
    https://www.luogu.com.cn/problem/P1114暴力,前缀和,稍加优化可以拿100,但是#1加强过后就AC不了了#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2e6;inta[maxn],n,f[maxn],ans,boy;intmain(){ cin>>n; for(inti=1;i<=n;i++) { scanf("%d",a......
  • 2023CSP复赛/NOIP备战模拟赛复盘集合
    20231003CSP-J模拟赛复盘这次模拟赛考的特别差,只有160。T1:一上来,虽然不那么打卡,但也挺简单,然后五分钟写完,对了对样例,对了,走人。T2:需要在\(O(nlogn)\)或者\(O(n)\)的时间复杂度求出每一个区间被覆盖的区间,这要怎么求啊?我想了半天也只知道\(O(n^2)\)怎么做,然后发现一个小时......
  • 2023CSP初赛游祭
    2023CSP初赛游记今日运势不错大号小号:在考试的前几天才下载到准考证,这个中国计算机学会C(虚)C(虚)F(服)一上去炸了,还不是我爸凌晨下载的,不然都下载不了。上午八点多来到一所像商场一样的学校--深实。里面的结构乱七八糟,窗明几净,不是商场是啥?经过在迷宫里找了半......
  • 2023CSP复赛游寄
    CSP2023游记优先看https://www.luogu.com.cn/paste/xegs7srzCSP终于来了,本想着这次pj300+,tg2=。看来要AFO了……7:40到了耀华考场,没想到已经有很多人来了,@Frank08,@2020luke,@mayingdi520都来了。。他们好像二十分就来了。过了一会,@2023FJZ来了,在他的外套里面穿着耀华的衣......
  • 2023CSP初赛备战复盘合集
    NOIP2010提高组复盘整套卷子讲解:noip2010初赛提高组试题详解-Dijkstra·Liu-博客园_noip2010提高组初赛试题解析-豆丁网Docin原题:luogu本文部分内容参考来自以上链接。总结:这次的卷子比较难,考了67.5,全机房第2,cwzdalao拿到了68分%%%,他的运气逆天,蒙对了程序输出题。......
  • 【luogu题解】P9749 [CSP-J 2023] 公路
    \(Meaning\)\(Solution\)这道题我来讲一个不一样的解法:\(dp\)在写\(dp\)之前,我们需要明确以下几个东西:状态的表示,状态转移方程,边界条件和答案的表示。状态的表示\(dp[i]\)表示到达第\(i\)个站点所需要的最少钱数,\(w[i]\)表示在使用最少钱数到达第\(i\)个站点时多余......
  • CSP-S 2023 复赛游记
    以前的游记太魔怔了,重新写一下。Day-3打了一场模拟赛,感觉A题有点ad-hoc,但是很经典,B题也很简单,构造题,一眼秒了,C题是真的不会,虽然很明显是一个DP,但是没有想出来如何设计状态,D题是简单的,想了一个主席树+树剖的做法,比较复杂,不愿写了,开摆100+100+0+0Day-2又打了......
  • CSP 2023 游记
    注:只报了S组。初赛Day-1在初赛考前承诺初赛过了跑1600m。Day1都比去年这个时候强这么多了还是怕初赛啊。我第一次喝下了红牛。别不信,以前真没喝过,,红牛很甜。下了车然后见到了yts,zhy等一众巨佬。简单聊了一会儿后开始找xhgua。找了半天找不着。眼尖貌似看到了wz的人来了,......