3 条题解
-
4
平平无奇的二分做法,带 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; }
信息
- ID
- 950
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 33
- 已通过
- 13
- 上传者