最讨厌的就是又臭又长还是全英文的题目


题目

题目概要(魔改):
就是一堆牛吃草,给你每头牛开始恰和结束恰的时间。一次只有一头牛能吃。
牛牛们不能一起吃。求最多多少牛可以恰。

输入描述:
*第1行:单个整数:N 
*第2..N + 1行:第i + 1行包含两个以空格分隔的整数:Si和Ei

输出描述:
*第1行:一个整数,代表可以一次放牧的最大母牛数量。


解析

显而易见的贪心,而且还是老套路了。
  • 这个题目简要就是。求一段区间内,不重合区间的最大区间数

贪心策略
  1. 这个贪心主要就是:按照结束时间来排序
  2. 为啥按照结束时间来排呢?因为上一个越早结束,下一个开始的时间就越早,选择的空间就越大
  3. 如果有重复的也没有关系哦,比如1-3和2~3,选啥都无所谓,反正我选了,你就不能选呗。

然后操作了:
  1. 这个题目可以直接定义一个结构体,然后结构体内置排序
  2. 这里我为了熟悉用pair,所以给pair写了一个排序函数,问题不大。

打代码
  1. 首先输入呗。初始化pair数组。
  2. 然后排序。
  3. 在判断计数,这里要保存上面的结束时间,因为要判断下一个能不能用嘛。
  4. 看我代码~


AC代码

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 5e4 + 7;
pair<int, int> info[MAX];
//全局变量区

bool cmp(const pair<int, int>& u, const pair<int, int>& v) {
    if (u.second == v.second) return u.first < v.first;
    return u.second < v.second;
}
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> info[i].first >> info[i].second;
    sort(info + 1, info + 1 + n, cmp);
    int ans = 0, en = 0;
    for (int i = 1; i <= n; i++)
        if (en <= info[i].first) {
            ans++;
            en = info[i].second;
        }
    cout << ans << endl;
    return 0;
}
//函数区