贪心法

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      if (①)
      {
        segment t = A[j];
        ②
      }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> A[i].a >> A[i].b;
  sort();
  int p = 1;
  for (int i = 1; i < n; i++)
    if (③)
      A[p++] = A[i];
  n = p;
  int ans = 0, r = 0;
  int q = 0;
  while (r < m)
  {
    while (④)
      q++;
    ⑤;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      if (①)
      {
        segment t = A[j];
        ②
      }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> A[i].a >> A[i].b;
  sort();
  int p = 1;
  for (int i = 1; i < n; i++)
    if (③)
      A[p++] = A[i];
  n = p;
  int ans = 0, r = 0;
  int q = 0;
  while (r < m)
  {
    while (④)
      q++;
    ⑤;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le m$）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      if (①)
      {
        segment t = A[j];
        ②
      }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> A[i].a >> A[i].b;
  sort();
  int p = 1;
  for (int i = 1; i < n; i++)
    if (③)
      A[p++] = A[i];
  n = p;
  int ans = 0, r = 0;
  int q = 0;
  while (r < m)
  {
    while (④)
      q++;
    ⑤;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

（2）（精明与糊涂）有 $N$ 个人，分为两类：
i) 精明人：永远能正确判断其他人是精明还是糊涂；
ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。