最差情况就是耐性最好的牛都在前面.
照此贪心, 排个序以后看从哪个牛开始耐不住就 OK
唯一要注意的就是所有牛的耐性都大于 \(N\) 的情况.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int MAXN = 1e5 + 20;
- inline int read()
- {
- int x = 0; char ch = getchar();
- while(!isdigit(ch)) ch = getchar();
- while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
- return x;
- }
- int N;
- int a[MAXN];
- int main()
- {
- cin>>N;
- for(int i = 1; i <= N; i++) a[i] = read();
- sort(a + 1, a + N + 1, greater<int>());
- int ans = N;
- for(int i = 1; i <= N; i++) if(a[i] < i - 1) {
- ans = i - 1; break;
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2723171.html