题目1：CF1108E1

题意

有一个包含 $n$ 个元素的整数数组 $a$ 和 $m$ 个区间 $[l_i, r_i](1 \le i \le m)$。现在要选出若干个区间，对于选出每个区间（每个区间只能选一次），将区间的元素都 $-1$ ，执行完操作后求 $\max\limits_{i = 1}^{n}\{a_i\} - \min\limits_{i = 1}^{n}\{a_i\}$ 的最大值。
$1 \le n, m \le 300$。

思路

枚举每个元素 $a_i$，把 $a_i$ 当成最大值，现在要让最小值最小。我们只能选择那些不包含 $a_i$ 区间，因为若一个区间包含 $a_i$，选这个区间不会让差值更大。所以模拟一遍以上操作即可。
时间复杂度
- 枚举每个元素：$O(n)$。
- 枚举每个区间：$O(m)$，每个区间将区间内所有元素 $-1$：$O(n)$。
- 找最小值：$O(n)$。
- 总时间复杂度：$O(n^2 \times m)$。

const int MAXN = 305;

struct Node{
  int l, r;
}b[MAXN];

int n, m, p, maxc, o, a[MAXN], e[MAXN], c[MAXN], ans[MAXN];

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= m; i++){
    cin >> b[i].l >> b[i].r;
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      e[j] = a[j];
    }
    int q = 0;
    for(int j = 1; j <= m; j++){
      if(b[j].r < i || b[j].l > i){ //区间不包含 a[i]
        c[++q] = j;
        for(int k = b[j].l; k <= b[j].r; k++){ //元素-1
          e[k]--;
        }
      }
    }
    int p = 1e7;
    for(int j = 1; j <= n; j++){ //求最小值
      p = min(p, e[j]);
    }
    if(a[i] - p > maxc){
      maxc = a[i] - p, o = q;
      for(int j = 1; j <= q; j++){ //记录答案
        ans[j] = c[j];
      }
    }
  }
  cout << maxc << '\n' << o << '\n';
  for(int i = 1; i <= o; i++){
    cout << ans[i] << ' ';
  }
  return 0;
}

题目2：CF1108E2

题意

有一个包含 $n$ 个元素的整数数组 $a$ 和 $m$ 个区间 $[l_i, r_i](1 \le i \le m)$。现在要选出若干个区间，对于选出每个区间（每个区间只能选一次），将区间的元素都 $-1$ ，执行完操作后求 $\max\limits_{i = 1}^{n}\{a_i\} - \min\limits_{i = 1}^{n}\{a_i\}$ 的最大值。
$1 \le n \le 10^5, 1 \le m \le 300$。

思路

此题题意和上题一样，就是 $n$ 可达 $10^5$，需要优化。
可以发现 $i$ 变到 $i + 1$ 时只有右端点为 $i$ 的区间内的元素 $-1$，左端点为 $i + 1$ 的区间内的元素 $+1$。可以发现 $a_1,a_2,\dots, a_i$ 中的最小值只有可能那些被减过的元素和 $i$ 还没变成 $i + 1$ 时最小值元素。因为 $a_{i + 2}, a_{i + 3}, \dots a_n$ 只可能 $+1$，所以求最小值不太好办，所以反着按上述方法做一遍即可。
找右端点为 $i$ 的区间和左端点为 $i + 1$ 的区间可以按左端点和右端点排两次序，再双指针一下即可。那么当最大值为 $a_i$ 时的答案为 $a_i - $ 左半部分的最小值和右半部分的最小值中小的那个。
时间复杂度
- 两次排序：$O(n \log n)$
- 每个区间只会被枚举两次，所以枚举区间：$O(m)$，每个还要将区间内元素 $-1$：$O(n)$。
- 总时间复杂度：$O(nm)$。

const int MAXN = 1e5 + 5, MAXM = 305;

struct Node{
  int l, r, id;
}b[MAXN];

bool cmp1(const Node &i, const Node &j){
  return i.r < j.r;
}

bool cmp2(const Node &i, const Node &j){
  return i.l < j.l;
}

int n, m, c, maxa = -1e6, mina = 1e6, a[MAXN], e[MAXN];
int lmin[MAXN], rmin[MAXN], maxcha[MAXN], ansx, ans[MAXM];

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    e[i] = a[i], maxa = max(maxa, a[i]), mina = min(mina, a[i]);
  }
  for(int i = 1; i <= m; i++){
    cin >> b[i].l >> b[i].r;
    b[i].id = i;
  }
  sort(b + 1, b + m + 1, cmp1);
  e[0] = 1e6, ansx = maxa - mina; //求一个也不选的答案
  for(int i = 1, j = 1; i <= n; i++){
    for(; j <= m && b[j].r == i - 1; j++){ //双指针枚举区间
      for(int k = b[j].l; k <= b[j].r; k++){
        e[k]--;
        if(e[lmin[i]] > e[k]){ //求最小值
          lmin[i] = k;
        }
      }
    }
    if(e[lmin[i - 1]] < e[lmin[i]]){ //和上一次的最小值比较
      lmin[i] = lmin[i - 1];
    }
    maxcha[i] = max(maxcha[i], a[i] - e[lmin[i]]); //更新最大值为 a[i] 的答案
  }
  sort(b + 1, b + m + 1, cmp2);
  for(int i = 1; i <= n; i++){
    e[i] = a[i];
  }
  for(int i = n, j = m; i; i--){
    for(; j && b[j].l == i + 1; j--){
      for(int k = b[j].l; k <= b[j].r; k++){
        e[k]--;
        if(e[rmin[i]] > e[k]){
          rmin[i] = k;
        }
      }
    }
    if(e[rmin[i + 1]] < e[rmin[i]]){
      rmin[i] = rmin[i + 1];
    }
    maxcha[i] = max(maxcha[i], a[i] - e[rmin[i]]); //更新最大值为 a[i] 的答案
  }
  for(int i = 1; i <= n; i++){ // 求最大差值
    if(ansx < maxcha[i]){
      ansx = maxcha[i], c = 0;
      for(int j = 1; j <= m; j++){
        if(b[j].r < i || b[j].l > i){
          ans[++c] = b[j].id;
        }
      }
    }
  }
  cout << ansx << '\n' << c << '\n';
  for(int i = 1; i <= c; i++){
    cout << ans[i] << ' ';
  }
  return 0;
}

题目3：CF1118D1

题意

有 $n$ 杯咖啡，第 $i(1 \le i \le n)$ 杯咖啡的咖啡因是 $a_i$，还有$m$ 个作业，一天的第 $k$ 杯咖啡 $x$ 可以让人做 $\max(0, a_x - k + 1)$ 个作业。问至少要几天才能做完 $m$ 个作业，若根本不能完成作业，输出 $-1$。
$1 \le n \le 100, 1 \le m \le 10^9, 1 \le a_i \le 100$。

思路

如果确定了天数，怎样让完成的作业尽可能多呢？首先考虑如果只有一天，一定要把所有咖啡都在这天喝了，如果把咖啡因少的放前面，后面的咖啡因多的会损失很多，而把多的放前面，少的放后面，少的可以做的作业更可能会是 $0$，而不是 $\max(0, a_x - k + 1)$，损失会小一些。
所以贪心思路：枚举天数，尽量把咖啡因多的放前面，看可以做的作业是否大于等于 $m$。
时间复杂度
- 枚举天数：$O(n)$.
- 计算可以做的作业：$O(n)$。
- 总时间复杂度：$O(n \times log n)$。
因代码简单，就不贴了，下一题代码改一下即可。

题目4：CF1118D2

题意

有 $n$ 杯咖啡，第 $i(1 \le i \le n)$ 杯咖啡的咖啡因是 $a_i$，还有$m$ 个作业，一天的第 $k$ 杯咖啡 $x$ 可以让人做 $\max(0, a_x - k + 1)$ 个作业。问至少要几天才能做完 $m$ 个作业，若根本不能完成作业，输出 $-1$。
$1 \le n \le 2\times10^5, 1 \le m \le 10^9, 1 \le a_i \le 100$。

思路

因为此题有单调性，所以二分天数再进行判断即可。
时间复杂度：$O(n \times log \ n)$。

const int MAXN = 2e5 + 5;

int n, m, a[MAXN], c[MAXN];

bool Check(int x){
  int s = 0;
  for(int i = n, j = 0; i && s < m; i--, j = (j + 1) % x){ //求最大可以完成作业的数量
    s += max(0, a[i] - c[j]), c[j]++;
  }
  fill(c, c + x, 0);
  return (s >= m);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  int l = 1, r = n + 1;
  while(l < r){ //二分天数
    int mid = (l + r) >> 1;
    if(Check(mid)){
      r = mid;
    }else{
      l = mid + 1;
    }
  }
  cout << (l == n + 1 ? -1 : l);
  return 0;
}

题目5：CF1108F

题意

给定一个 $n$ 个点 $m$ 条边且无重边自环的无向带权连通图。问要将至少多少条边的边权 $+1$ 才能使最小生成树唯一且边权和与原来的最小生成树一样？
$1 \le n \le 2 \times 10^5, n - 1 \le m \le 2 \times 10^5$，每条边的边权满足 $ \ge 1$ 且 $\le 10^9$。

思路

如果已经选完了边权 $ < k$ 的边了，那么边权为 $k$ 的边有以下两种情况：
- 加入当前边后有环了，那就不可能加入最小生成树。
- 加入当前边后无环了，那就可能加入最小生成树。
再将这些边每次从这些可能的中选一条出来加入生成树，注意同一值的边权可能加入多条。
从这些可能加入最小生成树的的边减去生成树内的边数量（也就是 $n - 1$）就是答案了。
时间复杂度
- 将 $m$ 条边排序：$O(m \times log \ m)$。
- 枚举每条边：$O(m)$，每次看是否可以加入：$O(log \ n)$。
- 总时间复杂度：$O(m \times (log \ m + log \ n))$。

const int MAXN = 2e5 + 5;

struct Edge{
  int x, y, w;
  bool operator <(const Edge &i)const{
    return w < i.w;
  }
}a[MAXN];

int n, m, c, fa[MAXN];

int Find(int x){
  return (fa[x] ? fa[x] = Find(fa[x]) : x);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    cin >> a[i].x >> a[i].y >> a[i].w;
  }
  sort(a + 1, a + m + 1);
  for(int i = 1, j; i <= m; i = j){
    for(j = i; j <= m && a[j].w == a[i].w; j++){
      int u = Find(a[j].x), v = Find(a[j].y);
      if(u != v){ //可能加入
        c++;
      }
    }
    for(; i < j; i++){ //将边加入生成树
      int u = Find(a[i].x), v = Find(a[i].y);
      if(u != v){
        fa[u] = v;
      }
    }
  }
  cout << c - (n - 1);
  return 0;
}