原题链接
题目描述
Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly 11 problem, during the second day — exactly 22 problems, during the third day — exactly 33 problems, and so on. During the kk -th day he should solve kk problems.
Polycarp has a list of nn contests, the ii -th contest consists of a_ia
i
?
problems. During each day Polycarp has to choose exactly one of the contests he didn’t solve yet and solve it. He solves exactly kk problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least kk problems that Polycarp didn’t solve yet during the kk -th day, then Polycarp stops his training.
How many days Polycarp can train if he chooses the contests optimally?
输入格式
The first line of the input contains one integer nn ( 1 \le n \le 2 \cdot 10^51≤n≤2?10
5
) — the number of contests.
The second line of the input contains nn integers a_1, a_2, \dots, a_na
1
?
,a
2
?
,…,a
n
?
( 1 \le a_i \le 2 \cdot 10^51≤a
i
?
≤2?10
5
) — the number of problems in the ii -th contest.
输出格式
Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.
题意翻译
Polycarp想要在另外一场比赛中训练，第一天他可以解决一个问题，第二天可以解决两个，以此类推，在第KK天他可以解决KK个问题
Polycarp有NN场比赛，第ii场比赛有aa_i
i
?
个问题，每一天他可以选择其中一个他尚未解决的比赛解决，但是要求a_ia
i
?
\ge≥KK,如果在第KK天尚未解决的比赛中没有大于等于KK的比赛，则Polycarp终止训练。
那么Polycarp最多能训练多少天呢？
输入输出样例
输入 #1复制
4
3 1 4 1
输出 #1复制
3
输入 #2复制
3
1 1 1
输出 #2复制
1
输入 #3复制
5
1 1 1 2 2
输出 #3复制
思路
就是所有比赛的题目总数从小到大排，然后定义一个K，然后如果当前比赛题目的数量大于K，那么k++.
最后输出k-1;
错误原因
因为一个比赛只可以打一次，所以直接往后遍历就行了，之前看成了只要题目数够就可以打；
错误代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,num[200005]={
0};map<int,int> res;cin>>n;for(int i=0;i<n;i++){
scanf("%d",&num[i]);}int k=0;num[n]=200006;while(1){
sort(num,num+n);int flag=lower_bound(num,num+n,k)-num;//cout<<num[flag]<<endl;if(num[flag]==200006){
break;}else{
num[flag]-=k;}k++;}cout<<k-1;return 0;
}
正确代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,num[200005]={
0};cin>>n;for(int i=0;i<n;i++){
cin>>num[i];}sort(num,num+n);int ans=1;for(int i=0;i<n;i++){
if(num[i]>=ans){
ans++;}}cout<<ans-1; return 0;
}