2025-12-13题目：Codeforces Round 1070 (Div. 2) A

约 398 字大约 1 分钟

2025-12-13

题外话

万事开头难。念叨了很久的每日一题，现在终于要尝试了。先来一个简单的。

题源

https://codeforces.com/contest/2176/problem/A

题意

给你一个数组 $a_i$ ，每次你可以选择一对 $i$ 和 $j$ ，他们满足 $i<j$ 且 $a_i>a_j$ ，并移除掉 $j$ 上的元素。数组长度将减少1，数组内其他元素顺序不变。问对于某数组 $a_i$ ，最优情况下，最多能执行几次这样的操作。

这是一道A题，数据规模很小，最大不超过100。

提示

操作的意思即“找到一对前大后小的，删除后面这个小的”。
某个数能不能被删除，取决于什么？

题解

不难发现，某个数能不能被删除，取决于前面有没有比它大的数。这里我们可以遍历每一个数字，再遍历它之前每一个数字，确定是否有这样一个数。这样的时间复杂度为 $O(n^2)$ 。

实际上，我们也可以发现，可以从头到尾遍历一次。对于每个数，我们把它视为比较的对象，如果后面一个数比它小，那么可以被移去；不比它小，那么可以将比较的对象变为这个不比它小的数，然后继续向后遍历。

部分代码

int n;
cin >> n;
int ans = 0;
n--;
int mx;
cin >> mx;
while (n--) {
	int b;
	cin >> b;
	if (b < mx) {
		ans ++;
	} else {
		mx = b;
	}
}
cout << ans << "\n";