首页 > 其他分享 >保龄球(二分)

保龄球(二分)

时间:2024-04-07 23:59:33浏览次数:24  
标签:二分 DL gs 打倒 位置 瓶子 发球 保龄球

题目描述

DL 算缘分算得很烦闷,所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了,所以技术上不成问题,于是他就想玩点新花招。

DL 的视力真的很不错,竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球,这样就能打倒一定数量的瓶子。

  1. ◯◯◯◯◯◯

  2. ◯◯◯ ◯◯◯◯ ◯

  3. ◯◯

  4. ◯ ◯◯ ◯

如上图,每个 “◯◯” 代表一个瓶子。如果 DL 想要打倒 33 个瓶子就在 11 位置发球,想要打倒 44 个瓶子就在 22 位置发球。

现在他想要打倒 m 个瓶子。他告诉你每个位置的瓶子数,请你给他一个发球位置。

输入格式

第一行包含一个正整数 n,表示位置数。

第二行包含 n 个正整数 ai​ ,表示第 i 个位置的瓶子数,保证各个位置的瓶子数不同。

第三行包含一个正整数 Q,表示 DL 发球的次数。

第四行至文件末尾,每行包含一个正整数 m,表示 DL 需要打倒 m 个瓶子。

输出格式

共 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。

对于 100% 的数据,1≤n,Q≤100000,1≤ai​,m≤10^9。

思路:暴力二分,结构体加sort函数;

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct aa{int g,w;};//创建结构体 
bool cmp(aa x,aa y)//sort函数判断条件 
{
	return x.g<y.g;
}
aa gs[100001];
int n,m,wt,l,mid,r;
 int main()
 {
 	cin>>n;
 	for(int i=1;i<=n;i++)
 	{
 		cin>>gs[i].g;
 		gs[i].w=i;
	 }
	 sort(gs+1,gs+1+n,cmp);
	 cin>>m;
	 for(int i=1;i<m;i++)
	 {
	 	cin>>wt;
	 	r=n+1,l=0;
	 	while(1+l<r)//利用二分查找位置 
	 	{
	 		mid=(r+l)/2;
	 		if(gs[mid].g<wt)l=mid;
	 		else r=mid;
		 }
		 if(gs[r].g!=wt)
		 cout<<"0"<<endl;
		 else
		 cout<<gs[r].w<<endl;
	 }
	 return 0;
 }

标签:二分,DL,gs,打倒,位置,瓶子,发球,保龄球
From: https://blog.csdn.net/2301_79963929/article/details/137483005

相关文章

  • 最长上升子序列——二分法
    前置设lowilow_ilowi​:长度为......
  • 二分+单调队列优化 2
    7-7列车调度(天梯赛选拔赛)https://pintia.cn/problem-sets/1768624240956489728/exam/problems/1768624240990044166?type=7&page=0火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以......
  • 二分+单调队列思想
    [AHOI2018初中组]分组(洛谷P4447)题目描述小可可的学校信息组总共有\(n\)个队员,每个人都有一个实力值\(a_i\)。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的\(n\)个队员分成若干个小组去参加这场比赛。但是每个队员都不会愿意与......
  • [蓝桥杯 2021 省 B] 杨辉三角形(二分查找+枚举)
        我们之前学过有关杨辉三角的一些性质,我们知道杨辉三角某个数等于左上和右上两个数相加,但是如果我们按照这个性质依次枚举每行每列,就会很容易超时,因此我们可以枚举列,再二分查找行来寻找满足要求的答案,我们可以先将列数到30,基本涵盖了所有的答案,通过组合数性质来二......
  • 二十五 4199. 公约数 (最大公约数|二分)
    4199.公约数(最大公约数|二分)思路:先用求最大公约数的模板求出a与b的最大公约数d,然后得到从1到d的全部公约数,最后利用二分法找到满足l≤x≤r条件的最大的公约数x。importjava.util.*;publicclassMain{privatestaticinta,b,q,l,r,cnt;privatestati......
  • 和为给定数(二分法)
    题目: 描述给出若干个整数,询问其中是否有一对数的和等于给定的数。输入共三行:第一行是整数n(0<n<=100,000),表示有n个整数。第二行是n个整数。整数的范围是在0到10^8之间。第三行是一个整数m(0<=m<=2^30),表示需要得到的和。输出若存在和为m的数对,输出两个整数,小的在......
  • 二分图相关
    基础最小点覆盖=最大匹配我们假设最小点覆盖的集合为\(V\),最大匹配的集合为\(E\),因为最大匹配中的边都互相不交,所以我们可以让最大匹配中的边的端点任意选择一个点,就有:\[|V|\ge|E|\]于是另一边不太好证明,我们就记住这一边的证明,感性理解~最大独立集=总点数-最小点覆......
  • [蓝桥杯 2022 国 A] 环境治理(二分 + 弗洛伊德)
        通过题目描述,我们得知如果枚举所有的天数,就不会通过所有的样例,因此我们可以通过二分来列举符合要求的天数,并且我们知道两个城市之间衡量的灰尘度标准就是灰尘度总和最小的那一段路径,也就是说我们需要寻找到权值和最低的那条路径,而我们知道每两个点之间都有路径......
  • ·跟着代码随想录刷力扣· ·数组部分· 2. 二分法
    leetcode题目:704二分法一、回顾顺序搜索(一)无序列表的顺序搜索,时间复杂度O(n)defsearch(self,nums:List[int],target:int)->int:pos=0whilepos<len(nums):ifnums[pos]==target:returnpos......
  • LeetCode 704.二分查找
    一、题目二、解题注:本文均是Java代码1、双闭区间写法classSolution{publicintsearch(int[]nums,inttarget){intleft=0,right=nums.length-1;while(left<=right){intmiddle=(left+right)>>>1;......