当前位置:网站首页>Interesting drink
Interesting drink
2022-07-06 09:25:00 【是小张张呀 zsy】
Interesting drink
Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink “Beecola”, which can be bought in n different shops in the city. It’s known that the price of one bottle in the shop i is equal to xi coins.
Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent mi coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of “Beecola”.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of shops in the city that sell Vasiliy’s favourite drink.
The second line contains n integers xi (1 ≤ xi ≤ 100 000) — prices of the bottles of the drink in the i-th shop.
The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of days Vasiliy plans to buy the drink.
Then follow q lines each containing one integer mi (1 ≤ mi ≤ 109) — the number of coins Vasiliy can spent on the i-th day.
Output
Print q integers. The i-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the i-th day.
Example
Input
5
3 10 8 6 11
4
1
10
3
11
Output
0
4
1
5
Note
On the first day, Vasiliy won’t be able to buy a drink in any of the shops.
On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.
On the third day, Vasiliy can buy a drink only in the shop number 1.
Finally, on the last day Vasiliy can buy a drink in any shop.
10的5次幂,必然要想到二分
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
int n,dis[100000],f,k;
bool book[2001];
char c[2001][2001];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>dis[i];
sort(dis,dis+n);
cin>>f;
for(int i=1;i<=f;i++)
{
cin>>k;
int mid=upper_bound(dis,dis+n,k)-dis;
cout<<mid<<endl;
}
return 0;
}
害,好久没用二分查找都忘了
二分模板
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
int n,dis[100009],f,k;
bool book[2001];
char c[2001][2001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>dis[i];
sort(dis+1,dis+1+n);
cin>>f;
for(int i=1;i<=f;i++)
{
cin>>k;
int l=1,r=n;
int mid;
while(l<=r)
{
mid=(r+l)/2;
if(dis[mid]>k)
r=mid-1;
else
l=mid+1;
//cout<<l<<r<<mid<<endl;
}
cout<<l-1<<endl;
}
return 0;
}
边栏推荐
- China medical check valve market trend report, technical dynamic innovation and market forecast
- Cost accounting [14]
- Medical colposcope Industry Research Report - market status analysis and development prospect forecast
- Record of force deduction and question brushing
- 入门C语言基础问答
- STM32 learning record: play with keys to control buzzer and led
- LeetCode#198. raid homes and plunder houses
- LeetCode#204. Count prime
- Automated testing problems you must understand, boutique summary
- STM32 learning record: input capture application
猜你喜欢
Learning record: how to perform PWM output
STM32 learning record: play with keys to control buzzer and led
入门C语言基础问答
MATLAB综合练习:信号与系统中的应用
How to become a good software tester? A secret that most people don't know
Leetcode notes - dynamic planning -day7
VS2019初步使用
JS --- BOM details of JS (V)
ucore lab 6
ucore lab5
随机推荐
FSM和i2c实验报告
学习记录:如何进行PWM 输出
STM32学习记录:LED灯闪烁(寄存器版)
Lab 8 文件系统
CS zero foundation introductory learning record
Market trend report, technical innovation and market forecast of Chinese hospital respiratory humidification equipment
Unpleasant error typeerror: cannot perform 'ROR_‘ with a dtyped [float64] array and scalar of type [bool]
LeetCode#62. Different paths
Cost accounting [19]
ucore lab 2
C语言必背代码大全
程序员的你,有哪些炫技的代码写法?
China chart recorder market trend report, technology dynamic innovation and market forecast
China medical check valve market trend report, technical dynamic innovation and market forecast
Printing quality inspection and verification system Industry Research Report - market status analysis and development prospect forecast
LeetCode#237. Delete nodes in the linked list
Cost accounting [13]
Learning records: serial communication and solutions to errors encountered
Research Report on market supply and demand and strategy of Chinese graphic screen printing equipment industry
Learning record: Tim - Basic timer