高效算法设计(六)

本节针对贪心算法中的区间相关问题做一系列阐述

区间相关问题

选择不相交区间

HDU2037
seg1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int maxn = 100 + 10;

class Seg {
public:
int l, r;
Seg(int _l = 0, int _r = 0) : l(_l), r(_r) {}
};

Seg seg[maxn];
vector<int> chooseID;
int n;

void init() {
chooseID.clear();
}

bool cmp(const Seg& lhs, const Seg& rhs) {
return lhs.r < rhs.r;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
init();
int lastR = -1;

_for(i, 0, n) scanf("%d%d", &seg[i].l, &seg[i].r);
sort(seg, seg + n, cmp);

lastR = seg[0].r;
chooseID.push_back(0);

_for(i, 1, n) {
if(seg[i].l >= lastR) {
chooseID.push_back(i);
lastR = seg[i].r;
}
}

printf("%d\n", (int)chooseID.size());
}
}

活动选择问题

活动串行执行
贪心算法很显然第一步是按照活动的结束时间排序

然后看看从当前时间出发,能不能安排此次活动?
如果不能的话,说明存在一个活动的时间过长了,导致溢出活动的截止日期
如果活动发生溢出的话,我们需要把过长的那个活动时间给替换掉

替换成什么活动呢?
用优先队列维护活动的持续时间,默认优先队列的top是活动时间最长的
如果当前的活动持续时间 < pq.top()
timing = timing - pq.top() + cur.持续时间
pq.push(cur.持续时间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int timing = 0;
sort(acts, acts + N);

_for(i, 0, N) {
Act& cur = acts[i];
// 看看能不能安排当前活动

if(timing + cur.持续时间 <= cur.结束时间) {
timing += cur.持续时间;
pq.push(cur.持续时间)
}
else if(!pq.empty() && cur.持续时间 < pq.top()) {
timing = timing - pq.top() + cur.持续时间;
pq.pop();
pq.push(cur.持续时间)
}
}

LA3507

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int maxn = 800000 + 10;
int N;

class Ord {
public:
int q, d;
Ord(int _q = 0, int _d = 0) : q(_q), d(_d) {}

bool operator< (const Ord& rhs) const {
return d < rhs.d;
}
};

Ord ords[maxn];

int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;

_for(t, 0, T) {
if(t) puts("");

cin >> N;
_for(i, 0, N) cin >> ords[i].q >> ords[i].d;

sort(ords, ords + N);

int timing = 0;
priority_queue<int> pq;

_for(i, 0, N) {
const Ord& cur = ords[i];

if(timing + cur.q <= cur.d) {
timing += cur.q;
pq.push(cur.q);
}
else if(!pq.empty() && cur.q < pq.top()) {
timing = timing - pq.top() + cur.q;
pq.pop();
pq.push(cur.q);
}
}

cout << pq.size() << endl;
}
}

区间选点问题

LA2519
seg2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int maxn = 1000 + 10;

class Seg {
public:
double l, r;
};

bool cmp(const Seg& lhs, const Seg& rhs) {
if(lhs.r != rhs.r) return lhs.r < rhs.r;
else return lhs.l > rhs.l;
}

Seg seg[maxn];
int n, d;

int kase = 1;
bool ok = 1;

void init() {
ok = 1;
}

int solve() {
sort(seg, seg + n, cmp);

int cur = seg[0].r, ans = 1;
_for(i, 1, n) {
if(seg[i].l - cur <= 1e-4) continue;

cur = seg[i].r;
ans++;
}

return ans;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &d) == 2 && (n || d)) {
init();
_for(i, 0, n) {
int x, y;
scanf("%d%d", &x, &y);
if(ok) {
if(y > d) {
ok = false;
continue;
}
double dist = sqrt(d * d - y * y);
seg[i].l = x - dist;
seg[i].r = x + dist;
}
}

// input finished, then solve the problem
printf("Case %d: ", kase++);

if(!ok) printf("-1\n");
else {
printf("%d\n", solve());
}
}
}

LA3835

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int maxn = 100000 + 10;
const double eps = 1e-4;
int L, D, N;

double dcmp(double x) {
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}

class Seg {
public:
double l, r;
Seg(double _l = 0, double _r = 0) : l(_l), r(_r) {}
};

bool cmp(const Seg& lhs, const Seg& rhs) {
if(dcmp(lhs.r - rhs.r) != 0) return dcmp(lhs.r - rhs.r) < 0;
else return dcmp(lhs.l - rhs.l) > 0;
}

typedef Seg Point;

Seg seg[maxn];

Seg getSeg(double x, double y) {
double d = sqrt(D * D - y * y);
double from = x - d, to = x + d;

if(dcmp(from) < 0) from = 0;
if(dcmp(to - L) > 0) to = L;
return Seg(from, to);
}

int solve() {
sort(seg, seg + N, cmp);

int ans = 1;
double cur = seg[0].r;

_for(i, 1, N) {
if(dcmp(seg[i].l - cur) < 0) continue;
if(dcmp(seg[i].l - cur) > 0) {
cur = seg[i].r;
ans++;
}
}
return ans;
}

int main() {
freopen("input.txt", "r", stdin);
while (cin >> L >> D >> N) {
_for(i, 0, N) {
double x, y;
cin >> x >> y;
seg[i] = getSeg(x, y);
}
cout << solve() << endl;
}
}

区间选点问题变形

在区间[1, n]内选择n个不同的整数
使得第i个整数在闭区间[li, ri]中

UVA11134

当区间两个端点的取值在[1, n]的时候
可以换一个角度思考
这时候贪心算法就相当于

为$x \in [1, n]$的每一个x, 选择一个区间
贪心选择思路是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_rep(x, 1, n) {
chose = -1, minr = n + 1;
// 让区间的右端点尽可能小, 维护一个minr
// minr的取值要尽量小
// vis < 0表示区间没有被选择过

_for(i, 0, n) {
if(seg[i].l <= x) {
if(vis[i] < 0 && seg[i].r < minr) {
minr = seg[i].r;
chose = i;
}
}
}
}

UVA11134

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool solve(Seg* seg, int* ans) {
fill(ans, ans + n, -1);

_rep(x, 1, n) {
int chose = -1, minr = n + 1;

_for(i, 0, n) {
if(x >= seg[i].l) {
if(ans[i] < 0 && seg[i].r < minr) {
minr = seg[i].r;
chose = i;
}
}
}

if(minr < x || chose < 0) return false;

ans[chose] = x;
}
return true;
}

选取等长的子线段

LA6279

LA6279

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int maxn = 100000 + 10;
const double eps = 1e-7;

int dcmp(double x) {
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}

class Seg {
public:
int from, to;
bool operator< (const Seg& rhs) const {
return from <= rhs.from;
}
};

Seg seg[maxn];
int n;

bool solve(const double len) {
double lastr = 0;
_for(i, 0, n) {
Seg& cur = seg[i];
lastr = max((double)cur.from, lastr) + len;

if(lastr > cur.to) return false;
}
return true;
}

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

void output(double x) {
double _p = floor(x + eps);
if(dcmp(_p - x) == 0) {
printf("%.0lf/1\n", _p);
return;;
}

int p = 1, q = 1;
double ans = 1;

_rep(i, 1, n) {
int pp = (int)(floor(x * (double)i + 0.5));
double tmp = (double)pp / i;

if(fabs(tmp - x) < fabs(ans - x)) {
p = pp;
q = i;
ans = tmp;
}
}

int g = gcd(p, q);
printf("%d/%d\n", p / g, q / g);
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1) {
_for(i, 0, n) {
scanf("%d%d", &seg[i].from, &seg[i].to);
}
sort(seg, seg + n);

double l = 1, r = (double)1000000.0 / n;
double mid;
assert(dcmp(l - r) <= 0);

_for(t, 0, 50) {
mid = (l + r) / 2;
if(!solve(mid)) r = mid;
else l = mid;
}

// output (l + r) / 2
//debug((l + r) / 2 );
output((l + r) / 2);
}
}

子线段选择

LA5845
LA5845

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int maxn = 100000 + 10;
int n;

class Seg {
public:
int from, to;

bool operator< (const Seg& rhs) const {
if(to != rhs.to) return to < rhs.to;
else return from < rhs.from;
}
};

Seg seg[maxn];

int solve() {
int ans = 0, last = -1;
_for(i, 0, n) {
Seg& cur = seg[i];

if(cur.to == last) continue;
if(cur.from <= last) {
last++;
}
if(cur.from > last) {
ans++;
last = cur.to;
}
}
return ans - 1;
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
scanf("%d", &n);
_for(i, 0, n) {
scanf("%d%d", &seg[i].from, &seg[i].to);
}

sort(seg, seg + n);

printf("%d\n", solve());
}
}