信奥赛-刷题笔记-二分篇-T2-P1918保龄球0529

总题单

​

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

二分篇题单

P1918 保龄球

https://www.luogu.com.cn/problem/P1918

题目描述

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

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

1. $◯◯◯$

2. $◯◯◯◯$

3. $◯$

4. $◯◯$

如上图，每个 “$◯$” 代表一个瓶子。如果 DL 想要打倒 $3$ 个瓶子就在 $1$ 位置发球，想要打倒 $4$ 个瓶子就在 $2$ 位置发球。

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

输入格式

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

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

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

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

输出格式

共 $Q$ 行。每行包含一个整数，第 $i$ 行的整数表示 DL 第 $i$ 次的发球位置。若无解，则输出 $0$。

输入输出样例 #1

输入 #1

5
1 2 4 3 5
2
4
7

输出 #1

3
0

说明/提示

【数据范围】

对于 $50\%$ 的数据，$1\le n,Q\le 1000,1\le a_i,m\le 10^5$。

对于 $100\%$ 的数据，$1\le n,Q\le 100000,1\le a_i,m\le 10^9$。

代码1-暴力

#include<bits/stdc++.h>using namespace std;
int n,q,tempq;
int arr[100010]; 
int arrq[100010]; 
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&arr[i]);}
//	for(int i=0;i<n;i++){
//		printf("%d ",arr[i]);
//	}cin>>q; for(int i=1;i<=q;i++){scanf("%d",&arrq[i]);}for(int i=1;i<=q;i++){//		printf("%d",tempq);// 哨兵bool flag = false; // 循环arr 每次都比较一下，如果相等就输出for(int j=1;j<=n;j++){if(arrq[i]==arr[j]){printf("%d\n",j);flag=true;break;}} if(!flag) printf("%d\n",0);}	return 0;
}
/*5
1 2 4 3 5
2
4
7
*/

会得80分

代码2-二分

#include<bits/stdc++.h>using namespace std;
int n,q,tempq;// 结构体保存值和初识坐标
struct blq{int num;int pos;
};blq arr[100010]; 
int arrq[100010]; // 二分查找 
int binary_search(int x){int l=1,r=n;while(l<=r){int mid=(l+r)>>1;if(arr[mid].num==x) return arr[mid].pos;else if(arr[mid].num<x) l=mid+1;else if(arr[mid].num>x) r=mid-1;}return 0;}bool cmp(blq b1,blq b2){if(b1.num>b2.num) return false;else return true;}int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&arr[i].num);arr[i].pos=i;}
//	for(int i=0;i<n;i++){
//		printf("%d ",arr[i]);
//	}cin>>q; for(int i=1;i<=q;i++){scanf("%d",&arrq[i]);}// 对保龄球进行排序sort(arr+1,arr+n+1,cmp);for(int i=1;i<=q;i++){printf("%d\n",binary_search(arrq[i]));}	return 0;
}
/*5
1 2 4 3 5
2
4
7
*/

#include<bits/stdc++.h>using namespace std;
long long n,m,a,ans;
struct data 
{long long h,H;
}N[100005];
bool cmp(data x,data y)
{return x.h<y.h;
}
bool pd(long long A,long long l,long long r)
{long long mid=(l+r)/2;if(N[mid].h==A){ans=N[mid].H;return true; }if(l>r)return false;if(A<=N[mid].h)return pd(A,l,mid-1);else return pd(A,mid+1,r);
}
int main()
{cin>>n;for(long long i=1;i<=n;i++){cin>>N[i].h;N[i].H=i;}sort(N+1,N+1+n,cmp);cin>>m;for(long long i=1;i<=m;i++){cin>>a;if(pd(a,1,n)){cout<<ans<<endl;}else cout<<0<<endl;}return 0;
}

代码3-哈希表

当然可以！下面是对你提供的 C++ 代码进行详细注释和头文件引用具体化后的版本。这个程序的功能是：

• 输入一个整数数组；
• 对每个查询值，输出它在数组中第一次出现的位置索引（从1开始）；
• 如果该值不在数组中，则输出 0。

---

✅ 完整带注释、具体头文件的版本

#include <cstdio>   // 提供 scanf / printf 等C语言标准输入输出函数
#include <iostream> // 提供 cin / cout 等C++标准输入输出流
#include <unordered_map> // 提供哈希表容器 unordered_map
#include <vector>   // 虽然未使用，但有时用于容器统一管理
using namespace std;// 全局变量声明
int n, q;                       // n表示数组长度，q表示查询次数
int arr[100010];                // 存储输入的数组元素（下标从1开始）
unordered_map<int, int> pos;    // 哈希表：key为数组中的值，value为其第一次出现的下标位置int main() {// 读取数组长度cin >> n;// 读取数组内容，并记录每个数字第一次出现的位置for (int i = 1; i <= n; i++) {scanf("%d", &arr[i]);       // 读取第i个元素// 如果当前数值还没有被记录过，就保存它的位置if (!pos.count(arr[i])) {pos[arr[i]] = i;        // key: 数值，value: 第一次出现的位置}}// 读取查询次数cin >> q;// 处理每个查询for (int i = 0; i < q; i++) {int x;scanf("%d", &x);            // 读取要查询的数值// 在哈希表中查找该数值是否存在if (pos.count(x)) {printf("%d\n", pos[x]); // 存在：输出其第一次出现的位置} else {printf("0\n");          // 不存在：输出0}}return 0;
}

---

🧠 补充说明

为什么使用 unordered_map？

• unordered_map 是基于哈希表实现的关联容器。
• 查找、插入、删除操作的平均时间复杂度为 O(1)。
• 非常适合用于这种“根据值查位置”的问题。

为什么记录的是“第一次出现”的位置？

• 因为我们只在第一次遇到某个值时才写入哈希表。
• 后续重复出现的值不会覆盖已有的位置信息。

时间复杂度分析

步骤	时间复杂度
读取并处理数组	O(n)
查询处理	O(q)
总体	O(n + q)

---

🚀 小技巧优化建议

如果你希望进一步提高性能（特别是在大数据量的情况下），可以加上以下两行代码来加速 IO 操作：

ios::sync_with_stdio(false);
cin.tie(nullptr);

这两个语句会关闭 cin 和 cout 与 scanf/printf 的同步，加快输入输出速度。

---

如果你还有其他问题，比如想了解底层原理、调试方法、或想把这个程序改成支持多组数据等，也可以继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}