PAT Basic Level 1060 爱丁顿数解题思路及AC代码 v0.93

本文主要是介绍PAT Basic Level 1060 爱丁顿数解题思路及AC代码 v0.93，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PAT 乙级 1060 爱丁顿数

- 1. 题目简述及在线测试位置
- 2. 基本思路
- 3. 完整AC代码

1. 题目简述及在线测试位置

1.1 根据输入数据求爱丁顿数。所谓爱丁顿数，就是出现N次、每次均大于N的整数N；举个栗子：3 3 2 ，爱丁堡数是2
1.2 在线测试位置： 1060 爱丁顿数

2. 基本思路

2.1 多重循环的思路必然导致部分测试点Fail，需要使用线性方式解决问题：扫描一次数据，就可以得到结果
2.2 通过数组存储数据，然后从大到小排序。分析爱丁堡数规律，得到：通过顺序遍历数组可以确定可能的最大爱丁堡数，通过变量Count标记爱丁堡数，当最大可能爱丁堡数Index 与 Count相等时，此时的Count值就是最终的爱丁堡数；当Index为 0 或负数时，说明录入数据小于等于1，不满足最小爱丁堡数1 ，遍历动作结束

//Index为索引值  Count为爱丁堡数,默认为0
Index = N;  Count=0; for (int i = 0; i < N; i++){while (Index >= a[i])//确定最大可能爱丁堡数Index--;if (Index <= 0)break;else if (Index == Count)break;else{Count++;if (Index == Count)break;}}

3. 完整AC代码

#include <algorithm>
#include <iostream>
using namespace std;#define MAX 100000bool compare(int a, int b)
{return a > b;
}int main()
{int a[MAX],N,Index,Count=0; //数组a  输入数  索引值  爱丁堡数cin >> N;Index = N;for (int i = 0; i < N; i++)cin >> a[i];sort(a, a + N,compare);for (int i = 0; i < N; i++){while (Index >= a[i])//确定最大可能爱丁堡数  Index--;if (Index <= 0)break;else if (Index == Count)break;else{Count++;if (Index == Count)break;}}cout << Count << endl;return 0;
}