当前位置: 代码迷 >> 综合 >> bzoj 5347: 冒泡排序
  详细解决方案

bzoj 5347: 冒泡排序

热度:69   发布时间:2023-10-29 04:47:20.0

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=5347

题解

和[Usaco2018 Open]Out of Sorts很像,然而没有想起来这个题怎么做。。
看回了那个题的题解才做出来2333
感觉药丸
都是一样的套路
其实还是考虑分隔符出现的时间
答案就是出现时间的最大值
也就是那题的ggg的最大值,当然,不需要对111取max

但是这题很卡常,你只可以循环一次
一开始,我和那题一样的写法,写成了

 for (int u=1;u<=n;u++)	f[a[u]]=u;int ans=0,mx=0;
for (int u=1;u<=n;u++)   {
    ans=max(ans,mx-u+1);mx=max(mx,f[u]);}

发现过不去

进一步思考,其实我们可以直接考虑每一个f[u]f[u]f[u]在哪里被减到最大值,自然是减数最小的时候,也就是枚举到他下一个的时候
于是就变成了

for (register int u=1;u<=n;u++)	ans=max(ans,u-a[u]);

加上输入是两个循环,还是过不去23333
最后,观察这个读入的方式
发现,可以直接写在输入里面
也就是

  for (register int u=1;u<=n;u++) 	{
    a[u]=u;S=(1LL*S*B+C)%D; swap(a[u],a[S%u+1]);ans=max(ans,u-a[u]);}

可以发现,并不会影响最大值
那么就可以做到一个循环了
于是就卡过去了!