首页 专栏 c++ 文章详情
关注作者
关注作者
0
PAT_甲级_1117 Eddington Number
乔梓鑫 发布于 2 月 26 日
题目大意
给定N天中每一天的骑行距离,如果有E天的骑行距离大于E,那么E就称之为艾丁顿数,请找出这个数字(尽可能大)
算法思路
既然要找到E的最大值,那么在每一天的骑行距离大于N的时候,E取得最大值N,这也是E的初始值。我们可以想到,(数组的下标值+1)其实就是第几天,那么将骑行的距离逆序排序,这样对于骑行距离大于(当前下标值+1)的位置,就是E的一个可能取值(E取下标值+1),我们为了取得最大值就是不断往右移动,知道第一次出现骑行距离小于等于当前下标值+1的位置,那么其左边就是E的最大值.
提交结果
AC代码
#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main() {
int n;
scanf("%d",&n);
int num[n];
for(int i=0;i<n;++i){
scanf("%d",&num[i]);
}
sort(num,num+n,cmp);
int E = n;// 没有解的时候,E为n
for(int i=0;i<n;++i){
if(num[i]<=i+1){
E = i;
break;
}
}
printf("%d\n",E);
return 0;
}
c++ 数据结构和算法
阅读 23 发布于 2 月 26 日
赞
收藏
分享
本作品系原创, 采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
PAT题解
关注专栏
乔梓鑫
主要分享个人学习经验和心得
468 声望
5 粉丝
0 条评论
得票 时间
提交评论
乔梓鑫
主要分享个人学习经验和心得
468 声望
5 粉丝
宣传栏
目录
▲
题目大意
给定N天中每一天的骑行距离,如果有E天的骑行距离大于E,那么E就称之为艾丁顿数,请找出这个数字(尽可能大)
算法思路
既然要找到E的最大值,那么在每一天的骑行距离大于N的时候,E取得最大值N,这也是E的初始值。我们可以想到,(数组的下标值+1)其实就是第几天,那么将骑行的距离逆序排序,这样对于骑行距离大于(当前下标值+1)的位置,就是E的一个可能取值(E取下标值+1),我们为了取得最大值就是不断往右移动,知道第一次出现骑行距离小于等于当前下标值+1的位置,那么其左边就是E的最大值.
提交结果
AC代码
#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main() {
int n;
scanf("%d",&n);
int num[n];
for(int i=0;i<n;++i){
scanf("%d",&num[i]);
}
sort(num,num+n,cmp);
int E = n;// 没有解的时候,E为n
for(int i=0;i<n;++i){
if(num[i]<=i+1){
E = i;
break;
}
}
printf("%d\n",E);
return 0;
}