7714（排列排序）

qiaochu2011 · 2024-04-30 14:24:32 · 题解

思路区：

在看到这道题后，我首先想到的方法就是差分。

具体思路是：循环遍历原数组，当遇到不应该出现在这个位置的数且这个数应该出现的位置在这个位置之后（为了去重）时,那么目前这个数的位置到它应该出现的位置的区间就要循环排序（也就是应标记）。当有其它需要被标记的区间有部分与已标记的区间重合时，重合部分也需要排序（标记）。

但如果循环遍历区间来标记的话太耗时了，容易TLE，所以我就想到了差分。

因为用差分标记的话，返回原数组后重合部分会比其他部分的值高。所以只需要在初始创建原数组数组时，将初始值设为0，之后返回原数组的数在判断时只要判断是否大于0（代码中用的是是不是等于0）。如果大于，那就sum++；否则不需要操作。 代码区：

#include <bits/stdc++.h>
using namespace std;
long long ti,n,a[2000000],c[2000000];//a是原数组，c是差分数组
int main(){
    ios::sync_with_stdio(0);//能省1毫秒省1毫秒（惜毫秒如金）
    cin>>ti;
    for(int ll=1;ll<=ti;ll++){
        cin>>n;
        int sum=0;//每次循环重新定义sum
        for(int i=1;i<=n;i++)c[i]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];//读入（cin YYDS）
        }
        for(int i=1;i<=n;i++){
            if(a[i]!=i&&a[i]>i){//其实只留下a[i]>i就行了
                c[i]+=1;//差分
                c[a[i]+1]-=1;//注意：一定是a[i]+1！
            }
        }
      for(int i=1;i<=n;i++){//回归本源
            a[i]=a[i-1]+c[i];
            if(a[i]!=0){
                sum++;//起初竟然把最重要的一步注释了QwQ
            }
        }
        cout<<sum<<endl;//直接输出就好，不需要再定义一个新数组 评测机YYDS
    }
    return 0;
}

END