3 条题解

  • 4
    @ 2026-10-28 8:57:18

    平平无奇的二分做法,带 log。

    楼上 zhengt 大佬有 O(n) 做法。

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 5;
    int a[N], b[N], n;
    bool c(int u) {
    	for(int i=1; i<u; i++) b[i] = a[i];
    	sort(b + 1, b + u);
    	int t = n - u;
    	for(int i=1; i<u; i++) {
    		if(b[i] > t) return 0;
    		t++;
    	}
    	return 1;
    }
    int main() {
    	ios :: sync_with_stdio(0);
    	cin.tie(0), cout.tie(0);
    	cin >> n;
    	for(int i=1; i<=n; i++) cin >> a[i];
    	int l = 1, r = n;
    	while(l <= r) {
    		int m = (l + r) >> 1;
    		if(c(m)) l = m + 1;
    		else r = m - 1;
    	}
    	cout << n - r << '\n';
    	return 0;
    }
    
    • @ 2026-10-28 8:58:28

      建议加强到 1e7 卡掉我的做法。

信息

ID
950
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
33
已通过
13
上传者