CodeForces 612D
奇妙的思维题。
题意：
给定n个区间，求被覆盖至少k次的区间（两端连续的区间可以合并）最少有多少个。
思路：
某个区间被覆盖至少k次，即这个区间的左端点包括左端点的前面应该至少包括给定的k个区间起点，且这些区间的终点至少有k个在这个区间右端点包括右端点的后面。
所以可以这么想：给定的区间的左端点会贡献1，右端点会贡献-1，然后根据这n个区间即2*n个数进行排序(如果数值相同，根据贡献从1到-1排)。然后扫一遍这2*n个数，当贡献达到k时，开始统计区间，统计到后面第一个贡献小于k的点。为什么统计到第一个贡献小于k的点，可以这么想，前面贡献达到k的区间段一直覆盖到这个第一个贡献小于k的点(这个点必是某个区间的右端点)，虽然右端点贡献是-1，但其实是闭区间，所以统计区间的时候这个点也应该被包括。
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e6+5;
struct node
{
int j, k;
bool operator<(const node a) const
{
if(j == a.j) return k > a.k;
return j < a.j;
}
} jk[maxn*2];
vector<pair<int, int> > vt;
int main()
{
int n, k, l, r;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; ++i)
{
scanf("%d %d", &l, &r);
jk[i*2].j = l;
jk[i*2].k = 1;
jk[i*2+1].j = r;
jk[i*2+1].k = -1;
}
n *= 2;
sort(jk, jk+n);
for(int i = 1; i < n; ++i) jk[i].k += jk[i-1].k;
for(int i = 0; i < n; ++i)
{
if(jk[i].k >= k)
{
l = jk[i].j;
while(i < n && jk[i].k >= k) ++i;
r = jk[i].j;
vt.push_back(make_pair(l, r));
}
}
cout << vt.size() << endl;
for(int i = 0, up = vt.size(); i < up; ++i)
{
cout << vt[i].first << " " << vt[i].second << endl;
}
return 0;
}继续加油~