当前位置:网站首页>饼干(考试版)
饼干(考试版)
2022-07-06 04:42:00 【Recurss】
题目背景
凌晨一点半,天刚蒙蒙亮,ly 在战场凹分,没吃午饭,饥肠辘辘的他从文具盒里翻出了一袋饼干......
这袋饼干有 n 块,分别称作第 1,2...n 块,第 i 块饼干的面积为 w [i],且 w [i] 是严格上升的(即 w [i + 1] > w [i]).
ly 需要吃 s 面积的饼干,并且他只会从中挑一块来吃,那么该块大于 s 的部分就会被扔掉.
于是勤俭节约的 ly 理所当然的会选择浪费面积最少的饼干来吃.
此外,众所周知,万事万物都会随着多种因素的变化而变化,当然 ly 需要吃的饼干的面积 s 也不例外
所以 ly 会询问你 q 次:当他需要吃的饼干的面积为 s [i] 时,他应该吃哪一块饼干.
(注意:每一次询问是独立的, 不是 第 i 次询问后,饼干会消失;若符合要求的饼干不只一块,输出编号最小的一块)
输入格式
对于每个测试点,有三行输入
第一行,输入两个正整数 n, q (n, q <= 20'0000),n 表示饼干的数量,q 表示询问的次数.
第二行,输入 n 个正整数 w [i],(w [i] <= 10'0000'0000) 表示第 i 块饼干的面积.
第三行,输入 p 个正整数 s [i], (s [i] <= 2'0000'0000), 表示 ly 第 i 次询问时,需要吃的饼干的面积.
输出描述
仅一行:q 个正整数,第 i 个数表示 ly 第 i 次询问时需要吃的饼干的编号.
样例输入
Copy to Clipboard
5 3 1 3 4 6 8 1 6 5
样例输出
Copy to Clipboard
1 4 4
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 1e9 + 10;
int w[N];
int sum[N];
int n,q;
int main(){
cin >> n >> q;
for(int i = 1;i <= n;i ++){
cin >> w[i];
}
while(q--){
int x;
cin >> x;
int pos = lower_bound(w + 1,w + 1 + n,x) - w - 1;
cout << pos + 1 << " ";
}
cout << endl;
}
边栏推荐
- Dry goods collection | Vulkan game engine video tutorial
- tengine 内核参数
- ETCD数据库源码分析——etcdserver bootstrap初始化存储
- 729. 我的日程安排表 I(set or 动态开点线段树)
- C'est un petit résumé de l'étude.
- Can CDC pull the Oracle table in full
- P2022 interesting numbers (binary & digit DP)
- 【HBZ分享】云数据库如何定位慢查询
- Complete list of common functions of turtle module
- Bill Gates posted his 18-year-old resume and expected an annual salary of $12000 48 years ago
猜你喜欢
11. Intranet penetration and automatic refresh
Meet diverse needs: jetmade creates three one-stop development packages to help efficient development
满足多元需求:捷码打造3大一站式开发套餐,助力高效开发
Recommendation | recommendation of 9 psychotherapy books
Coreldraw2022 new version new function introduction cdr2022
Bill Gates posted his 18-year-old resume and expected an annual salary of $12000 48 years ago
捷码赋能案例:专业培训、技术支撑,多措并举推动毕业生搭建智慧校园毕设系统
Introduction to hashtable
Digital children < daily question> (Digital DP)
A blog to achieve embedded entry
随机推荐
关于imx8mp的es8316的芯片调试
Complete list of common functions of turtle module
捷码赋能案例:专业培训、技术支撑,多措并举推动毕业生搭建智慧校园毕设系统
P3500 [POI2010]TES-Intelligence Test(二分&离线)
The implementation of the maize negotiable digital warehouse receipt standard will speed up the asset digitization process of the industry
【HBZ分享】云数据库如何定位慢查询
IPv6 comprehensive experiment
[Yu Yue education] reference materials of complex variable function and integral transformation of Northwestern Polytechnic University
[network] channel attention network and spatial attention network
优秀PM必须经历这3层蜕变!
flink sql 能同时读多个topic吗。with里怎么写
RTP GB28181 文件测试工具
[detailed steps of FreeRTOS shift value for the first time]
What should the project manager do if there is something wrong with team collaboration?
Platformio create libopencm3 + FreeRTOS project
Uva1592 Database
[数学建模] 微分方程--捕鱼业的持续发展
[HBZ share] reasons for slow addition and deletion of ArrayList and fast query
Excellent PM must experience these three levels of transformation!
coreldraw2022新版本新功能介绍cdr2022