一、题意

给你n条线段（线段端点为整数，n<=100000），输入保证线段间没有包含关系，且保证有解。
现在要求将每条线段截取长度为1的一小段，使得截取后的所有线段之间的空隙数目最少。
输出空隙的最少数目。

二、解析

  • 一开始用了一种比较复杂的方法：
    将所有线段按右端点排序后，每个线段尽量靠左边选取长度为1的片段，并维护一个remain值，表示该长度为1的片段右侧的空余长度（也就是可以动态右移多少长度）；还要维护一个cur值，表示当前已经选取的1片段的最右端位置。然后每次当发现当前线段与上一线段的1片段（cur值）之间有空隙时，首先检查remain能否填充这个空隙，若能，则将该空隙填充；若不能则说明这个空隙必须存在，即ans++。每次判定完一个片段需要更新remain值、cur值。
    这算是一种比较完备的思路，具体见后面代码。

  • 后来在网上发现一种简单一些的思路：
    由于题目中已经保证有解，因此其实根本不需要判定是否放得下，只需要执行贪心策略即可：即还是按照线段的右端点排序，然后第一个线段选取最靠右边的长度为1的片段（贪心），然后后续线段就紧靠着选取即可。若发现无法紧靠，即必然有空隙，则ans++；否则就一定能放得下。这种方法就只需要维护一个cur值表示当先选取的1片段得最右端即可。
    唯一要细节处理得就是，若当前线段与已选取1片段得最右端重合，则不需要改变cur值，因为题目保证有解，所以这里隐含得操作实际上是，将前面的所有片段左移1个单位，然后再将当前1片段放在这里。

三、代码

  • 比较完备的代码 
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5, INF = 1 << 30;
struct section{
    int l, r;
    bool operator < (const section& rhs) const {
        return r < rhs.r || r == rhs.r && l < rhs.l;
    }
} a[maxn];
int kase, n;

int main(){
    cin >> kase;
    while(kase --){
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> a[i].l >> a[i].r;
        sort(a, a + n);
        int ans = 0, remain = INF, cur = a[0].l;
        for(int i = 0; i < n; i ++){
            if(cur + 1 > a[i].r) ans ++, cur = a[i].l + 1;
            else if(cur < a[i].l){
                if(a[i].l - cur <= remain) remain -= a[i].l - cur;
                else ans ++, remain = INF;
                cur = a[i].l + 1;
            }
            else cur ++;
            remain = min(remain, a[i].r - cur);
        }
        cout << ans << endl;
    }
}
  • 比较取巧的代码 
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
struct section {
    int l, r;
    bool operator < (const section& rhs) const {
        return r < rhs.r || r == rhs.r && l < rhs.l;
    }
} a[maxn];
int kase, n;

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> a[i].l >> a[i].r;
        sort(a, a + n);
        int cur = a[0].r, ans = 0;  // 贪心：第一个片段靠最右边放，之后的依次紧靠
        for(int i = 1; i < n; i ++) {
            if(a[i].l > cur) ans ++, cur = a[i].r;
            else if(a[i].r == cur) continue;
            else cur ++;  // 由于线段端点为整数，所以只要右端不相等，就至少大1，一定足够放
        }
        cout << ans << endl;
    }
}

四、归纳

  • 要仔细看清楚题目，说不定题目没有你想的那么复杂....
  • 大多数时候，题目的输入全为整数值，这代表“偏移量”等要么为0，要么为1，这可能是简化题意的关键