B. Interesting drink(水题 二分)

题意:输入一组数据,再输入一个数(多组输入),判断在这组数据中,这个数大于等于多少个数。

题解:思路很简单,就是去找有多少个比该数小的数就行了,使用二分查找,这样省时间(普通for循环会超时,呜呜呜)

ACcode:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>

typedef long long ll;
using namespace std;

int main()
{
int n, x[100091], q, m;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i];
sort(x + 1, x + n + 1);
cin >> q;
while (q--)
{
int ans=0;
int mid, low = 1, high = n;
cin >> m;
if (m < x[1])
cout << "0" << endl;
else if (m >=x[n])
cout << n<< endl;
else
{
while (low <= high)
{
mid = (low + high) / 2;
if (m >= x[mid])
{
ans = mid;
low = mid + 1;
}
else if (m < x[mid])
{
high = mid - 1;
}
}
cout << ans << endl;
}
}
return 0;
}

原文地址:https://www.cnblogs.com/Uiney117/p/14207156.html