NOIP学习小站一、求最值
1.max/min
max/min函数用于求两个对象的最大值/最小值，还可以通过第3个参数指定比较函数。如果两个对象是结构体或者类变量，可以在结构体或类中重载<运算符，这样就可以方便地使用max/min函数来求极值。
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//重载<运算符
bool operator < (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
//重载ostream运算符，可以直接用cout输出Point变量
ostream& operator<<(ostream &os,const Point &p){
os<<"("<<p.x<<","<<p.y<<")";
return os;
}
//用于max/min判断两个元素关系的比较函数
bool cmp(const int &x,const int &y){
return abs(x)<abs(y);
}
int main()
{
cout<<max(-231,120)<<endl;
cout<<min(-231,120)<<endl;
//通过指定比较函数求最值
cout<<max(-231,120,cmp)<<endl;
cout<<min(12,-210,cmp)<<endl;
//求结构体变量的最值
cout<<max(Point(-2,-1),Point(1,1))<<endl;
cout<<min(Point(-2,-1),Point(1,1))<<endl;
return 0;
}2.max_element/min_element
max_element/min_element用来求序列的最值，返回值是指向最值的指针（或迭代器）。也可以指定一个比较函数用于判断两个元素的关系。
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//重载<运算符
bool operator < (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
//重载ostream运算符，可以直接用cout输出Point变量
ostream& operator<<(ostream &os,const Point &p){
os<<"("<<p.x<<","<<p.y<<")";
return os;
}
bool cmp(const int &x,const int &y){
return abs(x)<abs(y);
}
int main()
{
const int N = 10;
int a[N] = {-5,-4,-3,-2,1,1,2,2,3,4};
cout<<*max_element(a,a+N)<<endl;
cout<<*min_element(a,a+N)<<endl;
//通过指定比较函数求最值
cout<<*max_element(a,a+N,cmp)<<endl;
cout<<*min_element(a,a+N,cmp)<<endl;
const int M = 5;
Point b[M] = {
Point(-5,-5),
Point(-2,-1),
Point(0,0),
Point(1,1),
Point(3,2)
};
//求结构体变量的最值
cout<<*max_element(b,b+M)<<endl;
cout<<*min_element(b,b+M)<<endl;
return 0;
}二、两个序列的关系
1.equal
equal(begin1,end1,begin2)用来判断序列\([begin1,end1)\)和序列\([begin2,begin2+end1-begin1)\)两个序列的元素是否完全相同：
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//重载==运算符
bool operator == (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y==b.x*b.x+b.y*b.y;
}
//重载ostream运算符，可以直接用cout输出Point变量
ostream& operator<<(ostream &os,const Point &p){
os<<"("<<p.x<<","<<p.y<<")";
return os;
}
bool cmp(const int &x,const int &y){
return abs(x)==abs(y);
}
int main()
{
int a[3] = {1,2,3};
int b[4] = {1,2,3,4};
//以a为准，查看a的元素是否与b依次相等
//这里即使数组b中元素数量多，结果仍然是true
cout<<equal(a,a+3,b)<<endl; //true(1)
for(int i=0;i<4;i++) b[i] *= -1;
cout<<equal(a,a+3,b)<<endl; //false(0)
cout<<equal(a,a+3,b,cmp)<<endl; //true(1)
Point pa[2] = {Point(-2,-2),Point(1,-1)};
Point pb[2] = {Point(2,-2),Point(1,1)};
cout<<equal(pa,pa+2,pb)<<endl; //true(1)
return 0;
}2.mismatch
mismatch(begin1,end1,begin2)用来查找序列\([begin1,end1)\)和序列\([begin2,begin2+end1-begin1)\)第一处元素不相等的位置。返回值是一个pair，pair的first成员是序列\([begin1,end1)\)中第一处出现不相等元素的位置，pair的second成员是序列\([begin2,begin2+end1-begin1)\)中第一处出现不相等元素的位置。如果没有找到（可知此时equal(begin1,end1,begin2)的返回值为true），那么mismatch(begin1,end1,begin2)的返回值pair的first成员等于end1。
#include<iostream>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
Point(int x,int y){
this->x = x;
this->y = y;
}
};
//重载==运算符
bool operator == (const Point &a,const Point &b){
return a.x*a.x+a.y*a.y==b.x*b.x+b.y*b.y;
}
//重载ostream运算符，可以直接用cout输出Point变量
ostream& operator<<(ostream &os,const Point &p){
os<<"("<<p.x<<","<<p.y<<")";
return os;
}
bool cmp(const int &x,const int &y){
return abs(x)==abs(y);
}
int main()
{
const int N = 3;
int a[N] = {1,-2,3};
int b[N] = {1,2,4};
pair<int*,int*> p = mismatch(a,a+N,b);
if(p.first != a+N){
cout<<*(p.first)<<" "<<*(p.second)<<endl;
}
p = mismatch(a,a+N,b,cmp);
if(p.first != a+N){
cout<<*(p.first)<<" "<<*(p.second)<<endl;
}
Point pa[N] = {Point(-2,-2),Point(1,-1),Point(5,-4)};
Point pb[N] = {Point(2,-2),Point(1,0),Point(-5,-4)};
pair<Point*,Point*> q = mismatch(pa,pa+N,pb);
if(q.first != pa+N){
cout<<*(q.first)<<" "<<*(q.second)<<endl;
}
return 0;
}3.includes
includes(begin1,end1,begin2,end2)用来判断升序序列\([begin2,end2)\)是否是升序序列\([begin1,end1)\)的子序列。默认情况下，要求两个序列都是升序序列，也可以通过指定比较函数处理两个序列是降序序列的情况：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[5] = {1,2,3,4,5};
int b[2] = {3,4};
//数组a、b均为升序序列
cout<<includes(a,a+5,b,b+2)<<endl; //true(1)
reverse(a,a+5);
reverse(b,b+2);
//数组a、b均为降序序列
cout<<includes(a,a+5,b,b+2,greater<int>())<<endl; //true(1)
return 0;
}