bzoj 5347: 冒泡排序

2024-08-27 01:55:38

考虑到最后a[i]都要等于i，并且每个 a[i] < i 的a[i] 一轮最多向前走一次，所以局数至少是 max{ i - a[i] }。

又因为对于a[i] < i来说，一轮不动意味着 a[i-1] < a[i] ，所以 i-1 - a[i-1] 是>= i - a[i] 的，所以要么该位置不是max{i - a[i]}的位置，要么就会向前移动，所以局数正好就是 max{ i - a[i] }啦。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=3e7+5;

int a[maxn],n,S,B,C,D,ans;

const int max(int &x,int &y){ return x>y?x:y;}

int main(){

	scanf("%d%d%d%d%d",&n,&S,&B,&C,&D);

	const int ha=D;

	for(int i=1;i<=n;i++){

		a[i]=i,S=(S*(ll)B+(ll)C)%ha;

		swap(a[i],a[S%(const int)i+1]);

		ans=max(ans,i-a[i]);

	}

	printf("%d\n",ans);

	return 0;

}

最新文章

热门文章