题解：P11639 Line Game

chenly8128 · 2025-01-30 16:22:06 · 题解

最难的是看懂题目。

本质上就是给出 n 条线段，并给出第 i 条线段上的 a_i 个关键点，允许删除总计最多 m-1 条不含关键点的子线段，问剩下的线段含有的点（不仅包括关键点）的总数是多少。

理解到这一步，直接使用整体减空白思想和贪心大法。

1. 首先，计算不删除任何子线段情况下，点的总数。
2. 接着，计算把每条线段中任意的相邻的两个关键点之间子线段删去，能够减少的点的个数。并存入一个数组 a。
3. 然后，a 从大到小排序。
4. 最后，从总点数中减掉 a 中大于 0 的至多前 m-1 项。

然后就好了，复杂度 O(an\log_2{an})，瓶颈在于排序。

CODE

// Author: chenly8128
// Created: 2025-01-30 15:58:36

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(void) {
    int res = 0;bool flag = true;char c = getchar();
    while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
    while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
    return flag ? res : -res;
}
vector <int> res;
vector <int> v;
int n,m,a;
ll sum = 0;
int main (void) {
    n = read();m = read();
    for (int i = 1;i <= n;i++) {
        a = read();
        v.clear();
        for (int i = 1;i <= a;i++) v.push_back(read());
        sort (v.begin(),v.end());
        for (int i = 1;i < a;i++)
            res.push_back(v[i]-v[i-1]-1);
        sum += v[a-1]-v[0]+1;
    }
    sort (res.begin(),res.end(),greater<int>());
    for (int i = 0;i < res.size();i++) {
        if (i >= m-1 || res[i] <= 0) break;
        sum -= res[i];
    }
    printf ("%lld\n",sum);
    return 0;
}