高效算法设计(六)

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

区间相关问题

选择不相交区间

HDU2037

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.持续时间)

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

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

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

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$, 选择一个区间
贪心选择思路是

_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;
            }
        }
    }
}

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

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

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());
    }
}