【竞赛拙见】1.#include ＜bits/stdc++.h＞头文件、例题：大理石在哪儿

       最近在学习算法，打算平时记录一下自己的进步与收获。

1、#include <bits/stdc++.h>头文件

       在刚刚入门C语言的同学中，常用的头文件通常是#include <stdio.h>，stdio.h是stand input & output的缩写，意思是标准输入输出文件。

       而在程序竞赛中，为了简单方便，我发现了一个可以说是很万能的一个头文件#include<bits/stdc++.h>，写了这个头文件之后基本就不用再写其他的头文件了，程序也因此变得简单。

以下面的程序举例：

#include <bits/stdc++.h>

using namespace std;
int  main ()
{
    return 0;
}

 

       为了实践上文所说的头文件，我们可以用一道经典算法题来解释一下。

2、例题：大理石在哪儿

       现有N个大理石，每个大理石上写了一个非负整数。首先把各数从小到大排序，然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1～N。（在样例中，为了节约篇幅，所有大理石上 的数合并到一行，所有问题也合并到一行。）

样例输入：

4 1

2 3 5 1

5 

5 2

1 3 3 3 1

2 3

样例输出：

CASE #1:

5 found at 4

CASE #2:

2 not found

3 found at 3

       在这道题中，可以发现需要先排序，之后再查找；

       排序的时候我们可以想到sort()函数，但是sort函数包含在头文件为#include<algorithm>的c++标准库中，回看上文，我们可以用头文件#include<bits/stdc++.h>代替，程序代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10000;
int  main ()
{
	int n,q,x,a[maxn],kase=0;
	while(scanf("%d%d",&n,&q)==2 && n){
		printf("CASE# %d:\n",++kase);
		for(int i=0;i<n;i++) scanf("%d",&a[i]);
		sort(a,a+n);
		while(q--){
			scanf("%d",&x);
			int p=lower_bound(a,a+n,x)-a;
			if(a[p]==x) printf("%d found at %d\n",x,p+1);
			else printf("%d not found\n",x);
		}
	}
	return 0;
} 

       编译这段程序，可以发现并没有报错，而且最后可以得出正确答案。

       上面的代码中除了sort()外，lower_bound()函数的作用是查找“大于或者等于x的第一个位置”。

注意：头文件#include<bits/stdc++.h>虽然很好用，但是在相关文档上并没有标准提到它，所以可能导致代码不可移植之类的问题，但是在现在越来越多的oj支持这个头文件了，所以在程序竞赛中使用目前没有太大问题。