O(n^2)不是过不了吗？！！

lyria_ya

2026-05-01 09:34:27

发布于：四川

16阅读

0回复

0点赞

题目来源：洛谷P2866
根据《深入浅出》一书以及普遍常识，O(n^2)暴力枚举会TLE。
神奇代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; ++i) cin >> h[i];
	long long ans = 0;  // 总和可能较大
	for (int i = 0; i < n - 1; ++i) {       // 最后一头牛看不到任何牛
		for (int j = i + 1; j < n; ++j) {
			if (h[j] >= h[i]) {             // 被挡住
				break;
			}
			ans++;                          // 能看到牛j
		}
	}
	cout << ans << "\n";
	return 0;
}