陶陶摘蘋果2（藍橋杯）+整數二分法和暴力法

題目描述

陶陶家的院子裡有一棵蘋果樹，每到秋天樹上就會結出n個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個30厘米高的闆凳，當她不能直接用手摘到蘋果的時候，就會踩到闆凳上再試試。

現在已知n個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達到的最大高度。假設她碰到蘋果，蘋果就會掉下來。請幫陶陶算一下,經過她的洗劫後，蘋果樹上還有幾個蘋果。

輸入格式

輸入包括兩行資料。第一行隻包括兩個正整數n(5< =n< =200)和m(60< =m< =200),表示蘋果數目和桃桃伸手可 達到的高度（以厘米為機關）。第二行包含n個100到200之間（包括100和200）的整數（以厘米為機關）分别表示蘋果到地面的高度，兩個相鄰的整數 之間用一個空格隔開。

輸出格式

輸出包括一行，這一行隻包含一個整數，表示陶陶不能夠摘到的蘋果的數目。

樣例輸入

10 110

100 200 150 140 129 134 167 198 200 111

樣例輸出

5

思路：

1.看到這個題首先想到的是二分，因為确切的具有某種性質的都可以進行二分，此題适合

2.再看一眼，資料範圍可真小，直接暴力,挨個周遊後找到第一個大于它的數，用總數減去它的數組下标就是最終的答案（從0開始的數組坐标會偏移1，否則還需要加1）

3.話不多說，直接上代碼

代碼1：（整數二分法）

#include<iostream>
#include<algorithm>

using namespace std;


int erfen(int a[],int l, int r,int x)
{
 
	while(l<r)//此模闆是找出具有某種性質的最後一個數
	{
		int mid=(l+r+1)>>1;
		if(a[mid]<=x) l=mid;
		else r=mid-1;
	 } 
	 return r;
	 
}
int a[250];
int main()
{
	int n, m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);//首先進行排序，預設從小到大
	m+=30;//所能達到的最大高度
	int ans=erfen(a,0,n-1,m);//二分法求出最後一個數
	if(ans==0&&a[ans]>m)//此處需要進行一下特判，ans=0具有兩種情況，一種是a[ans]<=m;另一種是大于m
	cout<<n<<endl;//不進行特判的話，此處會扣分
	else
	cout<< n-ans-1<<endl;
}
           

代碼2（暴力法）

#include<iostream>
#include<algorithm>

using namespace std;


int erfen(int a[],int l, int r,int x)
{
 
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(a[mid]<=x) l=mid;
		else r=mid-1;
	 } 
	 return r;
	 
}
int a[250];
int main()
{
	int n, m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	m+=30;
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]>m)
		break;
	}
	cout<<n-i<<endl;
	return 0;
}


           

最後，如果對二分法存有疑問的話，部落客建議可以去看一下我寫的另一篇題解，是關于基礎算法的的，建議可以先練一下那個題，附上連結：

洛谷OJ - P1182 - 數列分段Section II（二分模闆）（多組輸入版本）