STL 简介

2019-05-26

view times

STL (Standard Template Library) 标准模板库

需要引入头文件：

1	#include <algorithm>

排序算法sort

用法一

对基本类型的数组从小到大排序：

1	sort(数组名+n1, 数组名+n2);

n1 和 n2 都是 int 类型的表达式，可以包含变量。
将数组下标范围为 [n1,n2) 的元素从小到大排列，下标为 n2 的元素不在排列区间内。

用法二

对元素类型为 T的基本类型数组从大到小排序：

1	sort(数组名+n1, 数组名+n2, greater<T>());

用法三

用自定义的排序规则，对任何类型 T 的数组排序，

1	sort(数组名+n1, 数组名+n2, 排序规则结构名());

排序规则结构的定义方式：

struct Rule
{
    bool operator() (const  T &a1, const T &a2){
        //若 a1 应该在 a2 前面，则返回 true。
        //否则返回 false。
    }
};

排序规则返回 true ，意味着 a1 必须在 a2 前面。
返回 false ，意味着 a1 并非必须在 a2 前面。

struct Rule1
{   //从大到小排列
    bool operator() (const  int &a1, const int &a2){
        return a1 > a2;
    }
};

struct Rule2
{   //按个位数从小到大排列
    bool operator() (const  int &a1, const int &a2){
       return a1%10 < a2%10;
    }
};

对结构体数组进行排列：

struct Student{
   char name[20];
   int id;
   double gpa;
};

struct Rule1
{   //按姓名从小到大排列
    bool operator() (const  Student &s1, const Student &s2){
    if(stricmp(s1.name<s2.name)<0)
        return true;
    return false;
    }
};

struct Rule2
{   //按 id 从小到大排列
    bool operator() (const  Student &s1, const Student &s2){
       return s1.id < s2.id;
    }
};

二分查找算法

STL 提供在排好序的数组上进行二分查找的算法。

用法一

在从小到大排好序的基本类型数组上进行二分查找。

1	binary_search(数组名+n1, 数组名+n2, 值);

查找区间为下标范围为 [n1,n2) 的元素，下标为 n2 的元素不在排列区间内。

在该区间内查找 “等于值”的元素，返回为true(找到）或 false（没找到）。

用法二

在用自定义排序规则排好序的、元素为任意的 T 类型的数组中进行二分查找。

1	binary_search(数组名+n1, 数组名+n2, 值, 排序规则结构名());

查找时的排序规则，必须和排序时(sort函数)的规则一致。

二分查找实现：

//在包含 size 个元素的 、从小到大排序的 int 数组 a里查找元素 p, 如果找到，则返回元素下标，如果找不到，则返回-1。 
int BinarySearch(int a[],int size,int p)
{
	int L=0; //左端点 
	int R=size-1; //右端点
	while(L<=R){
		int mid=L+(R-L)/2; //防止 L+R 过大溢出
		if(a[mid]==p)
			return mid;
		else if(p>a[mid])
			L=mid+1;
		else 
			R=mid-1;
	} 
	return -1;
}

例一

求下面方程的一个根： $f(x) =x^3-5x^2+10x-80 = 0$
若求出的根是 a，则要求 $|f(a)| <= 10^-6$

解法：对 f(x) 求导，得 $f’(x)=3x^2-10x+10$ 。由一元二次方程求根公式知f’(x)= 0 无解，因此 f’(x) 恒大于 0。故f(x) 是单调递增的。易知 f(0) < 0 且 f(100)>0,,所以区间 [0,100]内必然有且只一个根。由于 f(x) 在[0,100]内是单调的，所以可用二分办法在区间 [0,100]中寻找根。

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

double ESP = 1e-6;
double f(double x){
	return x*x*x-5*x*x+10*x-80;
}
int main(int argc, char** argv) {

	double root,y;
	double x1=0,x2=100;
	root = x1+(x2-x1)/2;
	y=f(root);
	while(fabs(y)>ESP){
		if(y>0)
			x2=root;
		else
			x1=root;
		
		root = x1+(x2-x1)/2;
		y=f(root);
	}
	
	printf("%.8f\n",root);

    return 0;
}

例二

寻找指定和的整数对
输入 n ( n<= 100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解 )。题中所有整数都能用int 表示。

解法一
1)将数组排序，复杂度是O(n x log(n))
2)对数组中的每个元素a[i],在数组中二分查找m-a[i]，看能否找到。复杂度log(n)，最坏要查找n-2次，所以查找这部分的复杂度也是 O(n ×log(n))
解法二
1)将数组排序，复杂度是O(n x log(n))
2)查找的时候，设置两个变量 i 和 j，i 初值是 0，j 初值是 n-1。看 a[i]+a[j],如果大于 m，则j-1，如果小于m就让 i+1。直到 a[i]+a[j] = m。

例三

Aggressive cows
总时间限制: 1000ms 内存限制: 65536kB

描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

输入

Line 1: Two space-separated integers: N and C
Lines 2..N+1: Line i+1 contains an integer stall location, xi

输出

Line 1: One integer: the largest minimum distance

样例输入

5 3
1
2
8
4
9

样例输出

3

提示
OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

思路

先得到排序后的隔间坐标 x1,…,xN
在 [L,R] 内用二分法尝试“最大最近距离”，D=(L+R)/2,(L,R初值为[1,1000000000/C])
若 D 可行，则记录该 D，然后在新的 [L,R] 中继续尝试。(L = D+1)。若 D 不行，则在新 [L,R] 中继续尝试。( R = D-1)

尝试方法：

第一头牛放在x1
若第 k 头牛放在 xi，则找到x（i+1）到 xN 中第一个位于[xi+D,1000000000]中的xj，第 k+1 头牛放在 xj。找不到这样的 xj，则说明不可行。

代码

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 1000000000
int a[100005];
int N,C;

int main(int argc, char** argv) {
	int i,t,s;
	scanf("%d%d",&N,&C);
	
	for(int i=0;i<N;i++)
		scanf("%d",&a[i]);	
	sort(a,a+N);
	
	int L=0;
	int R=MAX/C;
	int D;
	while(L<=R){
	D = L+(R-L)/2;
	int pre=0;
	t=1;
	
	for( i=1;i<N;i++){
		if(a[i]-a[pre]>=D)
        	{
          	  pre=i;
       	      t++;
       	 }
	}	
	
	if(t>=C){
	
		s=D;
		L=D+1;
	}
	else
		R=D-1;
	
	}
	
	printf("%d",s); 
	
    return 0;
}