题意

• 有 n 个怪物，第 i 个怪物存活于时刻区间 $[l_i, r_i]$，具有攻击力 $w_i$
• 选择一个非负整数时刻 x 发出攻击，可以攻击到 $x, x + T, x + 2\times T, x + 3\times T, \dots$ 这些时刻
• 如果某个怪物的存活区间中没有遭受过任何攻击，那么其就会造成对应 $w_i$ 的破坏
• 求选择哪一个非负整数时刻 $x$ 进行攻击，能够使得攻击的怪物破坏总和最低，输出这个总和

思考

• 重要结论一：x 只可能在区间 $[0, T- 1]$ 中选择
  • 如果选择了一个超过 $T$ 的 $x$，也就是说 $x \ge T$
  • 那么选择 $x - T$ 一定不会变差
  • 因为选择 $x - T$ 能够攻击到：$x - T, x, x + T, x + 2\times T,\dots$
  • 其包含了选择 $x$ 进行攻击时能够攻击到的所有时刻，所以答案不会变差
• 重要结论二：对于存活区间长度超过 $T$ 的怪兽，其不管选择什么时刻攻击都能干掉它
  • 可以发现如果区间长度超过 $T$，那么其必然包含了 $[0, T-1]$ 的所有余数
  • 所以不论选择 $[0, T- 1]$ 的哪个时刻发起攻击，都能够干掉这个怪兽

部分分

• 特殊性质 1：$1 \le n \le 10;\ 1 \le l_i,r_i,T \le 100$（20 分）
  • 直接枚举发起攻击的时刻 $[0, T-1]$
    • 再在 $[1, 100]$ 中把被攻击到的点都标记
  • 然后计算每一个区间 $[l_i, r_i]$ 是否被枚举的攻击时刻攻击
    • 直接扫描区间 $[l_i, r_i]$ 中是否有被攻击到的点即可
  • 取没被攻击怪兽伤害值总和最小的作为答案
  • 时间复杂度：$O(T\times n \times 100)$
• 特殊性质 2：$1 \le n \le 10^5;\ 1 \le l_i,r_i,T_i \le 10^5$（30 分）
  • 没有特殊解

题解

• 可以发现能够发出攻击的区间只需要考虑 $[0, T- 1]$
• 那么很自然想法，将每一只怪兽的存活区间，映射到 $[0, T-1]$ 中，看从哪些位置发出攻击能够干掉这只怪兽
• 对于长度超过 $T$ 的怪兽区间，直接默认死亡（不予考虑）
• 对于长度小于 $T$ 的区间将其平移到 $[0, T-1]$ 以内
  • $l_i \bmod T$ 且 $r_i \bmod T$
  • 分情况讨论，若现在 $l_i \le r_i$
    • 那么说明在 $[l_i, r_i]$ 间发起攻击能够干掉一只 $w_i$ 的怪兽
  • 若现在 $l_i > r_i$
    • 那么说明在 $[0, r_i]$ 和 $[l_i, T-1]$ 这两个区间中发起攻击能够干掉一只 $w_i$ 的怪兽
• 前缀和统计 $[0, T-1]$ 的每一个时刻能够消灭多少攻击力的怪兽取最大值减去即可

code

const int N = 1e5 + 9;

int sum[N];

void solved() {

  // 共 n 个怪物，每隔 m 单位时间攻击一次
  int n, m;	cin >> n >> m;

  int s = 0;
  while(n --) {
    // 当前怪物存活于 [l, r]，攻击力为 w
    int l, r, w;	cin >> l >> r >> w;

    // 如果存活区间长度至少为 m，这个怪物一定会死亡，无需考虑
    if(r - l + 1 >= m) continue;
    s += w;

    l %= m, r %= m;
    if(l <= r) sum[l] += w, sum[r + 1] -= w;
    else sum[0] += w, sum[r + 1] -= w, sum[l] += w, sum[m] -= w;
  }

  // 计算前缀和
  int mx = 0;
  for(int i = 0; i <= m - 1; i ++) {
    if(i != 0) sum[i] += sum[i - 1];
    mx = max(mx, sum[i]);
  }

  cout << s - mx;

  return ;
}