题目描述
小飞最近迷上了一个叫绝地求生的游戏. 不过他的技术并不好, 假设他的战斗力是 x. 不过, 他的战斗力是由心情来定的, 每天都不同. 现有一群 (1≤n≤100000) 也是玩绝地求生的朋友, 他们也有战斗力. 小飞想找一些比自己强的人玩, 提高自己的战斗力, 如: 小烨, 小祖, 小明等.
小飞一共玩了 m 天, 假设其他人的战斗力不变. 问: 小飞每天可以找到多少比自己强的人.
输入输出格式
输入格式
第一行, 输入一个 n, 表示有 n 个朋友;(1≤n≤100000)
第二行输入 n 个朋友的战斗力; 每个朋友战斗力不超过 long int(已有序);
第三行输入一个 m, 表示有 m 天;(1≤m≤100000)
接下来 m 行, 表示小飞每天的战斗力;(小飞战斗力不超过 int 范围).
输出格式
共 m 行, 每一行小飞每天找到的人数.
输入输出样例
输入样例
- 5
- 1 1 3 5 5
- 3
- 0
- 2
- 5
输出样例
5
3
0
题解
二分查找模板题, 暴力即可.
- #include<iostream>
- using namespace std;
- int n,m,a[100005],k[100005],mid;
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- }
- cin>>m;
- for(int i=1;i<=m;i++)
- {
- cin>>k[i];
- }
- for(int i=1;i<=m;i++)
- {
- for(int low=0,high=n+1;;)
- {
- mid=(low+high)/2;
- if(mid==low||mid==high)
- {
- cout<<n-mid;
- break;
- }
- else if(a[mid]<=k[i])
- {
- if(a[mid+1]>k[i])
- {
- cout<<n-mid;
- break;
- }
- else
- {
- low=mid;
- }
- }
- else
- {
- if(a[mid-1]<=k[i])
- {
- cout<<n-mid+1;
- break;
- }
- else
- {
- high=mid;
- }
- }
- }
- if(i<m) cout<<endl;
- }
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-2945376.html