PAT乙1060 愛丁頓數二分 &&&&&& 1056——1060

PAT乙1060 愛丁頓數二分 &&&&&& 1056——1060
1060 愛丁頓數(25 分)
英國天文學家愛丁頓很喜歡騎車。據說他為了炫耀自己的騎車功力,還定義了一個“愛丁頓數” E ,即滿足有 E 天騎車超過 E 英里的最大整數 E。據說愛丁頓自己的 E 等於87。
現給定某人 N 天的騎車距離,請你算出對應的愛丁頓數 E(≤N)。
輸入格式:
輸入第一行給出一個正整數 N (≤10
​5
​​ ),即連續騎車的天數;第二行給出 N 個非負整數,代表每天的騎車距離。
輸出格式:
在一行中給出 N 天的愛丁頓數。
輸入樣例:
10
6 7 6 9 3 10 8 2 7 8
輸出樣例:
6

直接二分

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,d[100005],e=0;
bool cmp(int a,int b){return a>b;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i  )
{
scanf("%d",&d[i]);
}
sort(d 1,d 1 n,cmp);
int l=1,r=n,mid;
while(l<=r)
{
mid=(l r)/2;
if(d[mid]>mid)
{
l=mid 1;
e=mid;
}
else
{
r=mid-1;
}
}
printf("%d\n",e);
return 0;
}

1056——1060
稍微總結一下,第一次卡時間
這裡寫圖片描述