P1918 保龄球 洛谷
2024-08-25 14:17:17
https://www.luogu.org/problem/show?pid=1918
题目描述
DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。
DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。
1 OOO
2 OOOO
3 O 4 OO
如上图，每个“O”代表一个瓶子。如果 DL 想要打倒 3 个瓶子就在 1 位置发球，想要打倒 4 个瓶子就在 2 位置发球。
现在他想要打倒 m 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。
输入输出格式
输入格式：
输入文件名为 bowling.in。
第一行包含一个正整数 n，表示位置数。
第二行包含 n 个正整数，第 i 个数。表示第 i 个位置的瓶子数，保证各个位置的瓶子数不同。
第三行包含一个正整数 Q，表示 DL 发球的次数。
第四行至文件末尾，每行包含一个正整数 m，表示 DL 需要打倒 m 个瓶子。
输出格式：
输出文件名为 bowling.out。
共 Q 行。每行包含一个整数，第 i 行的整数表示 DL 第 i 次的发球位置。若无解，则输出 0。
输入输出样例
输入样例#1：
5
1 2 4 3 5
2
4
7
输出样例#1：
3
0
说明
【数据范围】
对于 50%的数据，1 ≤ n,Q ≤ 1000，1 ≤ai,M ≤ 10^5
对于 1000%的数据，1 ≤ n,Q ≤ 100000，1 ≤ai,M ≤ 10^9
#include <algorithm>
#include <iostream>
#include <cstdio>
#define maxn 100015
using namespace std; int n,m;
int b,l,r,midd;
bool judge;
struct node
{
int id,x;
}a[maxn]; bool cmp(node aa,node bb)
{
return aa.x<bb.x;
} int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>a[i].x;
a[i].id=i;
}
sort(a+,a+n+,cmp);
cin>>m;
for(int i=;i<=m;i++)
{
cin>>b;
l=;r=n;judge=false;
while(l<=r)
{
midd=(l+r)/;
if(b<a[midd].x)
{
r=midd-;
continue;
}
if(b>a[midd].x)
{
l=midd+;
continue;
}
if(b==a[midd].x)
{
judge=true;
break;
} }
if(judge)
{
cout<<a[midd].id<<endl;
continue;
}
else
cout<<<<endl;
}
return ;
}
二分查找+快排
最新文章
- 自定义控件之 圆形 / 圆角 ImageView
- caffe_实战之两个简单的例子（物体分类和人脸检测）
- 模拟实现SQL Server字段列显示的数据类型
- Postgre cannot insert multiple commands into a prepared statement
- 3.C#中泛型类的进一步探讨
- 使用Chrome DevTools的Timeline分析页面性能
- 关于ADMM的研究（一）
- DDD 应对具体业务场景，Domain Model 重新设计
- ddos攻击和cc攻击的区别和防护！！
- hive发杂数据结构的使用，struct，array，map
- [kuangbin带你飞]专题二十二 区间DP-E-POJ - 1651
- pinpoint初始化hbase脚本报错
- jvm系列二、JVM内存结构
- Swift搭建本地http服务器，实现外部视频即时播放
- JQ_返回顶部
- Spring之redisyi一主一从复制（非哨兵模式）
- 10.29 scrum meeting newbe软件团队工作分配
- avalon学习教程
- [漏洞复现]CVE-2018-4887 Flash 0day
- #leetcode刷题之路25- k个一组翻转链表