sort函数和lower_bound函数

青旅半醒 2022-05-11 10:10 155阅读 0赞

大理石在哪？刘汝佳：《算法竞赛入门经典》p108

**题目：**

> 现有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

分析：略。

代码：

#include<iostream>
    #include<algorithm>
    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)
    	{
    		cout<<"CASE# :"<<++kase<<endl;
    		for(int i=0;i<n;i++)
    			cin>>a[i];
    		sort(a,a+n);//默认从小到大排序
    		while(q--)
    		{
    			cin>>x;
    			int p=lower_bound(a,a+n,x)-a;//查找>=x的第一个位置 
    			if(a[p]==x)
    				cout<<x<<" found at "<<p+1;
    			else
    				cout<<x<<" not found"; 
    		} 
    	}
    	return 0;
    }

结果：

![70][]

**正文：**

一、sort函数：对给定区间元素进行排序

1、默认按照升序排列。

2、可以修改排序方法，使之从大到小排序。

3、也可以对按结构体内的元素进行排序。（这个注意下）

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct student
    	{
    		int grd1;
    		int grd2;
    	}stu[5]={
       {5,6},{5,4},{3,8}};
    
    bool comp1(int i,int j)
    {
    	return i<j;
    }
    
    bool comp2(int i,int j)
    {
    	return i>j;
    }
    
    bool comp3(student &x,student &y)//多看两遍 
    {
    	if(x.grd1!=y.grd1)
    		return (x.grd1>y.grd1);
    	if(x.grd2!=y.grd2) 
    		return (x.grd2>y.grd2);
    }
    
    
    int main()
    {
    	int i;
    	int a[6]={23,52,12,43,33,29};
    	//sort(a,a+6,comp1);
    	sort(a,a+6,comp2);
    	for(i=0;i<6;i++)
    		cout<<a[i]<<" ";
    	cout<<endl<<endl;	
    		
    	
    
    	sort(stu,stu+3,comp3);
    	for(i=0;i<3;i++)
    	{
    		cout<<stu[i].grd1<<" "<<stu[i].grd2<<endl;
    	} 
    	
    	return 0;
    }

二、lower\_bound函数：在给定区间内查找 大于等于x的第一个位置。（为二分查找）(upper\_bound,亦然)

**参考文章：**

**sort:**

**[http://www.cplusplus.com/reference/algorithm/sort/?kw=sort][http_www.cplusplus.com_reference_algorithm_sort_kw_sort]**

**[https://blog.csdn.net/weixin\_41112564/article/details/81488307][https_blog.csdn.net_weixin_41112564_article_details_81488307]**

**lower\_bound:**

[http://www.cplusplus.com/reference/algorithm/lower\_bound/?kw=lower\_bound][http_www.cplusplus.com_reference_algorithm_lower_bound_kw_lower_bound]

[70]: /images/20220511/6c67cd7d09894955927c00a2fe9d231c.png
[http_www.cplusplus.com_reference_algorithm_sort_kw_sort]: http://www.cplusplus.com/reference/algorithm/sort/?kw=sort
[https_blog.csdn.net_weixin_41112564_article_details_81488307]: https://blog.csdn.net/weixin_41112564/article/details/81488307
[http_www.cplusplus.com_reference_algorithm_lower_bound_kw_lower_bound]: http://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound