Week3：区间覆盖——局部贪心
C-区间覆盖
题目内容
数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t] (1<=t<=1,000,000)，不可能办到的话输出-1。
输入格式
输入包括多组数据，对于每组数据：
第一行：n和t。
第二行至n+1行: 每一行一个闭区间。
输出格式
对于每组数据，输出选择的区间的数目，不可能办到输出-1。
每组数据的输出单独占一行。
样例
3 10
1 7
3 6
6 10
2
天坑警告
这些区间覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)；
但是如果(1,2)之后是(4,5)，则(1,2)不覆盖3。
可以和时间类比理解：
比如第一秒包括[1,2)左闭右开的时间区间。
前两秒和第三第四秒可以覆盖整个前四秒~
另外本题数据量较大，不要使用iostream。
解题思路
这道题天坑奇多，而且存在时间限制(1000ms)。本人写了十多个小时，大概6个版本，一度心态崩溃到想要放弃。结果今天开了个新.cpp，重新从零开始写了一遍结果过了，就很玄学。
我现在觉得可能是我最后AC时用的是ios::sync_with_stdio(false)下的cin而不是scanf改变了最终的结局。(这都要怪万恶的编译器 )
以下给出WA了12次之后AC的代码及其分析。
看到这道题，我们采取贪心策略：
对于每组数据，先按a 从小到大排序，区间1 的起点如果大于s（初始s=1），无解；否则选择起点在s 的最长区间。选择区间[ai, bi] 后的起点应设置为bi，并切掉bi 之前的部分。
首先，本体数据量非常大，那么如果使用cin和cout几乎肯定是会超时的(事实证明确实会超时)，所以在这里我们使用scanf或者ios::sync_with_stdio(false)下的cin。
然后我们使用一个向量数组来存放输入的这些区间，进行上述排序。
设置一个变量len，初始值为0。
然后我们使用一个for循环来遍历数组中的所有区间，对于这些区间我们有：
- 当前区间i的b都比当前的s要小，那么选这个肯定是浪费，弃之，continue。
- 当前区间i的a小于等于s+1(注意)，更新len。len的含义为所有a小于等于s+1的区间中，b到s的距离最大时的距离，此举是贪心的核心，即对每次覆盖，都尽可能挑选能覆盖范围最大的那个区间，这样就能够尽可能少地选区间。
- 当前区间i地a大于s+1时，说明选择这个区间会出现空洞，即不能全覆盖，不服题意，由于事先已经排序过，所以之后的区间全部不符合，因此break。
跳出循环之后，我们检测len的数值。如果len还是0，说明上述的三种情况中，不存在第二种情况。而如果只是第一种和第三种情况，那么就会有空洞，因此说明这组数据是无结果的，因此我们输出-1，结束这组数据的处理。
在处理完之后，我们把当前的s移到上面那个使len最大的那个区间的b处。然后重复以上从for循环开始的一系列操作，直到s==t；
示例代码
#include <iostream>
#include <algorithm>
#include <vector>
const int badans = -1;
using namespace std;struct TC
{int a;int b;
};vector<TC> arr;bool cmp(const TC& m, const TC& n)
{return m.a < n.a;
}int main()
{ios::sync_with_stdio(false);int n, s, t;while (cin >> n >> t){arr.clear();s = 0;//因为下面代码中使用s+1来实现整点覆盖，由于s初始值应该是1，所以这里预设为0int ans = 0;bool isok = true;for (int i = 0; i < n; i++){TC temTC;cin >> temTC.a >> temTC.b;arr.push_back(temTC);}sort(arr.begin(), arr.end(), cmp);//一个可选的剪枝//如果不用这个，那么nowpos的那个位置恒设为-1，即i=0int nowpos = -1;while (s < t){int len = 0;int themaxone = 0;//记录使len最大的那个区间for (int i = nowpos + 1; i < arr.size(); i++){if (arr[i].b <= s) continue;if (arr[i].a <= s + 1)//整点覆盖{int x = arr[i].b - s;if (x > len){len = x;themaxone = i;nowpos = i;}}else break;}if (len == 0)//无解，直接输出-1并break出循环{cout << badans << endl;isok = false;break;}ans++;s = arr[themaxone].b;//刷新当前s}//如果不是通过break跳出循环的话说明是有解的if (isok) cout << ans << endl;}return 0;
}
发布评论