库特君的面条

╰+哭是因爲堅強的太久メ 2022-05-11 02:18 149阅读 0赞

题目：库特君在吃面条

他将面条放在数轴上，每根面条对应数轴上的两个点a和b，他想知道在任意两根面条不重叠（端点可以重叠）的情况下最多能选出多少根面条。

1<= n <=100

\-999<= a<b<=999

> **输入：**
> 
>     第一行一个整数N
>     接下来，N行，每行2个空格分隔的整数a和b（注意：a有可能大于b）
> 
> **输出：**
> 
>     一个数的答案

**样例：**

> **输入：**
> 
>     3
>     6  3
>     1  3
>     2  5
> 
> **输出：**
> 
>     2

**原理：**

> **可以将其转化成坐轴的形式，在坐标轴上应该有个顺序，故**
> 
> **第一步必须对输入的线条（非面条）进行排序，这里涉及到两种排序，行间以及行内排序；**
> 
> **第二步比较关系，如果发生重叠，则重叠的线条的左端点一定在上一条面条右端点左侧，换言之，成为一个面条的条件是，线条的左端点必须在上一条面条的右侧（端点可以重合）。**
> 
> **注意：利用面条成立的条件作为判定依据比较好。**

#include<iostream>
    #include<algorithm> //排序方法
    #include<vector>
    using namespace std;
    
    bool DSC(pair<int,int> a,pair<int,int> b) {return a.first<b.first;} //排序方法：根据左值进行降序排序（大到小）
    
    int countnoodles(vector<pair<int,int>> line)
    {
        int result = 0;
    
        sort(line.begin(),line.end(),DSC);	//行间排序
    
        //法1：满足成为面条的条件，则面条数加1，且将上一根面条重新设置
        //法2：若不满足条件，将下一条的线拿过来比较与上一条面条作比较，较法1麻烦
        int pre = 0;//上一根
        for(unsigned int i = 1; i<line.size();i++)  //若用int 会提示，因为vector被定义为unsigned int类型。同类型比较
            if(line[pre].second >=line[i].first)
            {
                result++;
                pre = i;
            }
            return result;
    }
    
    int main()
    {
    	int N;
    	vector<pair<int,int>> line;
    	cout<<"输入线条数N：";
    	cin>> N;
    	cout<<"输入具体的线条（a  b）:";
    	for(int i = 1;i<=N;i++)
    	{
            int a,b;
            string ch;
            cin >>a>>b;
            if (a<b)	//行内排序
                line.push_back(make_pair(a,b));	//赋值方式***********
            else
                line.push_back(make_pair(b,a));	
    	}	
    	cout <<endl<<"库克的面条数为："<<countnoodles(line);
    
    	system("pause");
    	return 0;
    
    }