【DSOI 2021】电子跃迁
题目背景
“如果能证明大统一理论，这个世界将焕然一新。”
“量子……量子……就差一点……”
“嘶……哦。我想我明白了。”
题目描述
在你的视野下，出现了一排电子，他们分别拥有不同的能量。你需要做的是通过将相邻电子互换的方法，将电子排的有序。有序是指：能量最小的电子放到最靠近原子核的左边，将第二小的电子放在第二……将能量最大的电子放在最右边。
可是，你发现电子轨道之间忽然出现了
m
m
m 个奇怪的力，使位于第
x
i
x_i
xi 个位置的电子和位于第
x
i
+
1
x_i+1
xi+1 个位置的电子无法进行交换。
你深信这个力将会颠覆当下的物理理论。你需要做的是将现在的一排电子排得尽量有序以发现其中规律。
尽量有序是指：在条件下，能量最小的电子尽量放到左边直至出现屏障，以此类推。
输入格式
第一行输入两个整数
n
,
m
n,m
n,m ，分别表示电子数量和力的数量。
第二行输入
n
n
n 个整数，表示初始电子排列，其中第
i
i
i 个数
a
i
a_i
ai 代表第
i
i
i 个电子拥有的能量。
第三行包含
m
m
m 个整数。其中第
i
i
i 个整数
x
i
x_i
xi 表示位于第
x
i
x_i
xi 个位置的电子和位于第
x
i
+
1
x_i+1
xi+1 个位置的电子无法进行交换的。
输出格式
输出一行 n n n 个整数，表示在这种情况下尽量有序的排列结果。
样例 #1
样例输入 #1
3 0
3 2 1
样例输出 #1
1 2 3
样例 #2
样例输入 #2
7 2
1 3 1 4 5 2 1
2 4
样例输出 #2
1 3 1 4 1 2 5
提示
对于
10
%
10\%
10% 的数据，满足
m
=
0
m=0
m=0；
对于另
20
%
20\%
20% 的数据，满足
n
≤
1000
,
m
≤
100
n \le 1000,m \le 100
n≤1000,m≤100；
对于
100
%
100\%
100% 的数据，满足
0
≤
n
,
m
≤
5
×
1
0
5
,
1
≤
x
i
≤
n
−
1
,
1
≤
a
i
≤
1
0
9
0 \le n,m \le 5 \times 10^5,1 \le x_i \le n-1,1 \le a_i \le 10^9
0≤n,m≤5×105,1≤xi≤n−1,1≤ai≤109。
C++实现
#include
#include
#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=x10+ch-‘0’;ch=getchar();}
return xf;
}
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;
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;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
标签：le,信奥,int,561,样例,电子,ch,xi,打卡 From： https://blog.csdn.net/rogeliu/article/details/144965243