专栏文章

题解：CF1898B Milena and Admirer

2025/05/18 19:24CF1898B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @mip9kc99
此快照首次捕获于: 2025/12/03 08:23
此快照最后确认于: 2025/12/03 08:23

思维 + 贪心

题意即每次操作可以选择一个位置，将这个位置的数拆分成两个正整数，显然拆分后的每个数只会比拆分前的数更小。

由于拆分后的数会变得更小，同时我们需要保证最终数列变为单调不降。显然从前往后正序遍历数组将无法保证当前位置拆分后是否满足整个序列单调不降，因此我们考虑贪心地从后往前倒序做，对于每次枚举到的位置，让其拆分出的数比后缀最小值小的同时尽可能地大。

考虑维护后缀最小值

mn

。

当 $a_i \le mn$ ，无需操作，同时更新最小值 $mn=a_i$ 。
当 $a_i \gt mn$ ，令 $k=\left \lceil \dfrac{a_i}{mn} \right \rceil$ ，则需要对 $a_i$ 这部分进行 $k-1$ 次操作，并且更新最小的值为 $\left \lfloor \dfrac{a_i}{k} \right \rfloor$ 。

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
typedef long long LL;
const int N=2e5+5;
int n;
int a[N];
void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	int mn;
	memset(&mn,0x3f,sizeof mn);
	LL ans=0;
	per(i,n,1){
		if(a[i]<=mn) mn=a[i];
		else{
			int k=(a[i]+mn-1)/mn;
			ans+=k-1;
			mn=a[i]/k;
		}
	}
	cout<<ans;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...