标签：200005 int Codeforces cc && 922 排序 Round
- 自豪的是D题做出来了，悲哀的是B题没能做出来
- C题的绝对值最小
- D题，DP存不下状态就把状态放进所求值中
- 比赛快结束的时候，我想，这个B题，它但凡需要我通过归并排序或者树状数组求逆序对，不比C题进制转化要难？于是我就猜了一个结论
- 结论是对的，但不幸的是，我编程实现的时候出错了
- 考虑怎样证明这个结论，发现此时任意操作都不会使结果更优
- 本质上是以“排序”为贪心策略
- 实现的时候可以将两个数组捆绑起来一起排序
- 要相信、也可以相信，自己是对的呀……
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[200005],b[200005],r[200005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n=read1();
for(int i=1;i<=n;i++)
{
a[i]=read1();
}
for(int i=1;i<=n;i++)
{
b[i]=read1();
r[b[i]]=i;
}
for(int i=1;i<=n;i++)
{
if(b[i]!=i)
{
r[b[i]]=r[i];
swap(a[i],a[r[i]]);
swap(b[i],b[r[i]]);
}
}
for(int i=1;i<n;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[n]);
for(int i=1;i<n;i++)
{
printf("%d ",b[i]);
}
printf("%d\n",b[n]);
}
return 0;
}
标签：200005,
int,
Codeforces,
cc,
&&,
922,
排序,
Round
From： https://www.cnblogs.com/watersail/p/18002149