题解 P7343 【【DSOI 2021】电子跃迁】

LinkZelda · 2021-02-11 23:17:05 · 题解

• 做法简述：

题意十分清晰，就是给定一个数列，和一些断点，我们容易发现，把断点升序排序后，原数列分成了若干个区间，题目转化为求在每一个断开的区间内进行升序排序。

注意到题目给出的数据范围比较大：N \leq 10^5，使用冒泡排序，插入排序等是 \mathit{O}(n^2) 的，不能通过。我们可以直接使用 algorithm 库中的 sort 排序，可以做到 \mathit{O}(n \log n) 的复杂度，可以通过本题 。

• 代码如下 :

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#define int long long

using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f; 
 } 

int n,m,a[500005],b[500005];

signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=m;i++)
        b[i]=read();
    sort(b+1,b+m+1); // 记得排序后才能分成若干个区间
    b[m+1]=n; // 把最后一个断点设成 n , 实现起来会比较方便
    for(int i=0;i<=m;i++)
        sort(a+b[i]+1,a+b[i+1]+1);
    for(int i=1;i<=n;i++)
        printf("%lld ",a[i]);
    return 0;
}