今年暑假不AC【區間貪心、貪心策略、c++】

作者: 執迷_4869 | 来源:发表于2020-01-29 18:58 被阅读0次

今年暑假不AC【區間貪心、貪心策略、c++】
世間
不貪為喜——讀通札記（1585）
😊大丈夫
捫心自問7---關於“貪”
貪
是夢
塘魚
滿滿的週末
人生三境

Problem Description

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

分析

正確的策略是，每次都選取結束時間最早的節目，然後拋棄與所作選擇衝突的節目，直到所有節目都處理完畢。該斷言的依據如下：
【命題一】如果選中節目a，則必須拋棄所有與a衝突的節目。
【命題二】如果拋棄節目a，一定存在與a衝突的節目b被選中了。
【命題三】如果最優解是集合 ${a, b, c, d, \cdots}$ ，不論先選擇其中的哪一個節目，必不會導致最優解中的其它節目被刪除。
【命題四】設集合 $A, B$ 是節目的集合且 $A\subseteq B$ ，則對於該問題， $B$ 的最優解中節目的個數不少于 $A$ 的最優解中節目的個數。
以上幾個命題都不言自明。
接著，設節目a是結束時間最早的節目，分兩種情況討論。
情況一：a不與任何其它節目衝突。則為了使能觀看的節目最多，應該要選擇a。
情況二：存在與a相衝突的節目。
由定理二知如果不選擇a，則必須選擇b，b是一個與a相衝突的節目。易知，由於a的結束時間最早，若c與a衝突，且c不是b，則c與b衝突。另外，可能存在一些節目，它們不與a衝突，但與b衝突。設選擇節目a，同時刪除與a衝突的節目后，剩餘的節目集合為 $R_a$ ，同樣定義 $R_b$ ，顯然 $R_b \subseteq R_a$ 。問題變為在 $R_a$ 或 $R_b$ 中的子問題。根據命題四，選擇節目a，得到的互不衝突的節目數都是最多的。
總之，不論何種情況，選擇a都是最優的。

代碼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n && n) {
        vector<vector<int> > programmes(n);
        for (int i = 0; i < n; ++i) {
            vector<int> programme(2);
            cin >> programme[0] >> programme[1];
            programmes[i] = programme;
        }

        // 按节目结束时间升序
        sort(programmes.begin(), programmes.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });

        vector<int> programme;
        int count = 0;
        for (int i = 0; i <programmes.size(); ++i) {
            auto programme2 = programmes[i];
            if (programme.size() == 2 && programme2[0] < programme[1] && programme2[1] >= programme[1]) {
            }
            else {
                programme = programme2;
                ++count;
            }
        }

        cout << count << endl;
    }
    return 0;
}