YTU OJ 2372：给牛照相

81 阅读 0 评论 54 点赞

我是靠谱客的博主危机招牌，这篇文章主要介绍YTU OJ 2372：给牛照相，现在分享给大家，希望可以做个参考。

给牛照相

题目描述

农夫约翰想给他的N (2 <= N <= 1,000,000,000) 头牛照相，这些牛站成一排分别编号为1..N。每张照片可以拍摄连续的一些牛，并且约翰想让每头牛至少出现在一张照片上。

不幸的是有一些牛脾气不合，不想出现在同一张照片上，不合的牛有K(1 <= K <= 1000)对。给出这K对不合关系，算一下约翰最少需要拍多少张照片。

输入

第1行，两个整数N和K

第2到K+1行，每行两个数A和B，表示位置在A和B的两头牛不合，因此不能在同一张照片中。

输出

一个整数，表示约翰最少需要拍多少张照片数。

样例输入

复制代码

样例输出

复制代码

1
3

提示

约翰需要拍3张照片。

第一张拍1－2号牛

第二张拍3－5号牛

第三张拍6－7号牛

//数据结构真是妙啊

//感谢YPA学长给的思路,太妙了！

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int a,b;
}a[1001];
bool cmp(node x,node y)
{
    return x.a<y.a;
}
int main()
{
    int s,i,j,l,t;
    int n,k;
    cin>>n>>k;
    int st=1;
    int cnt=1;
    for(i=0;i<k;i++)
    {
        cin>>a[i].a>>a[i].b;
        if(a[i].a<a[i].b)
        {
            swap(a[i].a,a[i].b);
        }
    }
    sort(a,a+k,cmp);
    for(i=0;i<k;i++)
    {
        if(a[i].b>=st)
        {
            cnt++;
            st=a[i].a;
        }
    }
    cout<<cnt<<endl;
    return 0;
}