题目链接:1117 Eddington Number (25分)
题意
给出N天的骑行路程,求满足E天骑行超过E公里,最大的E。
分析
将路程按照从大到小排序,10 9 8 8 7 7 6 6 3 2
从1开始当第i天路程a[i] - 1 >= i时,满足E天超过E公里,将i一直增加知道不满足条件时停止,即a[i] - 1 < i。则最大天数为 E = i - 1;
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;
const int maxn = 100010;
int a[maxn];
bool cmp(int a, int b) {
return a > b;
}
int main(int argc, char** argv) {
int n, e;scanf("%d", &n);for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);}sort(a + 1, a + 1 + n, cmp);e = n;for (int i = 1; i <= n; i++) {
if (a[i] - 1 < i) {
e = i - 1;break;}}printf("%d", e);return 0;
}