【PAT甲级】1117 Eddington Number (25分)

题意:

输入一个正整数N(<=100000),接着输入N个非负整数。输出最大的整数E使得有至少E个整数大于E。

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[];
int num[];
map<int,int>mp;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
int cnt=;
for(int i=;i<=n;++i)
cin>>a[i];
sort(a+,a++n);
for(int i=;i<=n;++i){
if(!mp[a[i]])
mp[a[i]]=++cnt;
++num[mp[a[i]]];
}
for(int i=cnt-;i;--i)
num[i]+=num[i+];
int ans=;
for(int i=n;i;--i){
int pos=upper_bound(a+,a++n,i)-a;
if(pos<=n&&num[mp[a[pos]]]>=i){
ans=i;
break;
}
}
cout<<ans;
return ;
}
上一篇:一键启动NameNode和DataNode--shell脚本


下一篇:PAT 甲级 1024 Palindromic Number (25 分)(大数加法,考虑这个数一开始是不是回文串)