TB椰程 TypeBuddy 打字搭子

贪心

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 609 字

每步取局部最优，需先证明全局最优

  • 算法
  • 贪心

前置内容

正文

// 贪心：每一步取局部最优
// 未必全局最优，需先证明
// 经典：区间按结束时间排序
// 例：最多不重叠区间数
#include <cstdio>
#include <algorithm>
using namespace std;
struct Seg { int l, r; } s[10005];
// 按右端点升序，早结束优先
bool cmp(Seg a, Seg b) { return a.r < b.r; }
int n, ans = 0, last = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &s[i].l, &s[i].r);
    // 排序后用贪心选区间
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        // 与上一区间不重叠才选
        if (s[i].l >= last) {
            ans++;
            // 更新末端点
            last = s[i].r;
        }
    }
    printf("%d", ans);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK