C++11(clang++ 3.9) 解法, 执行用时: 41ms, 内存消耗: 1164K, 提交时间: 2020-08-24 09:52:11

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

int n,s[100010],dp[100010];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	sort(s+1,s+n+1);
	
	for(int i=1;i<=n;i++){
		if(s[i]<=i)dp[i]=max(dp[i-1],dp[i-s[i]]+1);
	}
	
	if(s[n]>n)cout<<"-1"<<endl;
	else cout<<dp[n]<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 41ms, 内存消耗: 1144K, 提交时间: 2020-09-10 12:14:19

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],mx[100005],dp;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i){
		dp=a[i]<=i?mx[i-a[i]]+1:0;
		mx[i]=max(mx[i-1],dp);
	}
	cout<<(dp?dp:-1);
}

Python3(3.9) 解法, 执行用时: 75ms, 内存消耗: 14568K, 提交时间: 2021-04-05 15:51:36

n=int(input())
a=list(map(int,input().split()))
a.sort()
if(n<a[-1]):
    print(-1)
else:
    a=a[:n-a[-1]]
    cnt=ans=0
    for i in a:
        cnt+=1
        if(cnt>=i):
            ans+=1
            cnt=0
    print(ans+1)