高效算法设计(四)

贪心算法有很多综合的应用
这里主要阐述一下如何在算法设计中
引入一些数学思想和算法分析的思想

训练题目以
《算法竞赛入门经典第二版》中第八章的题目为主

水题

中途相遇法

算法分析, 先把最大和最小的装起来看看行不行?
可以，就把最大最小的装袋，然后 $R-1$

1
2
3

[i, R]
R--相当于出队列
i++相当于i出队列

不可以呢？ $i+1$ , 就是 $i$ 单独装袋

const int maxn = 100000 + 10;
int n, M;
int l[maxn];

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

    _for(i, 0, n) cin >> l[i];
    sort(l, l + n, greater<int>());

    int ans = 0;
    _for(i, 0, n) {
        ans++;
        if(l[i] + l[n - 1] <= M) n--;
    }
    cout << ans << endl;
}

暴力枚举

LA6196
LA6196

const int maxn = 1000 + 10;
int n;

int main() {
    freopen("input.txt", "r", stdin);
    string D[maxn], P;

    while(cin >> n && n) {
        _for(i, 0, n) cin >> D[i];
        sort(D, D + n);

        string L = D[n / 2 - 1], R = D[n / 2];

        P = "A";
        _for(i, 0, L.size()) {
            while(P[i] <= 'Z' && P < L) P[i]++;
            if(P[i] <= 'Z' && L <= P && P < R) break;

            if(L[i] != P[i]) P[i]--;
            P += "A";
        }
        cout << P << endl;
    }
}

区间非连续子序列预处理

有一类问题称为
在区间中选出若干个点(不一定连续), 这若干个点组成的子序列
需要满足一定条件

UVA11491

const int maxn = 100000 + 10;
char buf[maxn];
int A[maxn];
int g[maxn][10];
int N, D;

void init() {
    Set(buf, 0);;
    Set(A, 0);
    Set(g, 0);
}

void initCal() {
    _rep(x, 0, 9) {
        int pos = N;
        _forDown(i, N - 1, 0) {
            if(A[i] == x) pos = i;
            g[i][x] = pos;
        }
    }
}

bool valid(int x, int L, int R, int E) {
    // can x valid in [L, R]
    return g[L][x] <= R && R - g[L][x] >= E;
}

int selectMax(int L, int R, int E, int& pos) {
    _forDown(x, 9, 0) {
        if(!valid(x, L, R, E)) continue;
        pos = g[L][x];
        return x;
    }
}

void solve(int E) {
    initCal();
    int L = 0;
    string ans;
    while (E--) {
        int pos;
        ans += selectMax(L, N - 1, E, pos) + '0';
        L = pos + 1;
    }
    cout << ans << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &N, &D) == 2 && N && D) {
        init();

        scanf("%s", buf);
        _for(i, 0, N) A[i] = buf[i] - '0';
        // input finished

        solve(N - D);
    }
}

图形旋转问题

LA5237
LA5237

const int maxn = 13;

class Point {
public:
    int x, y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}

    bool operator< (const Point& rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }

    bool operator== (const Point& rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

Point operator+ (const Point& lhs, const Point& rhs) {
    return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point operator- (const Point& lhs, const Point& rhs) {
    return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point rotate(const Point& s, const Point& r) {
    Point dv = s - r;
    Point ans = r + Point(dv.y, -dv.x);
    return ans;
}

class Line {
public:
    Point from, to;
    bool vertical;

    Line rot(const Point& r) {
        Line ret;
        ret.from = ::rotate(from, r);
        ret.to = ::rotate(to, r);
        return ret;
    }

    void normalize() {
        vertical = (from.x == to.x);
        if(vertical) {
            if(from.y > to.y) swap(from.y, to.y);
        }
        else {
            if(from.x > to.x) swap(from.x, to.x);
        }
    }
};

int n;
vector<Line> lines;

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

int main() {
    freopen("input.txt", "r", stdin);
    while(cin >> n && n) {
        init();

        Line l;
        l.to = Point(1, 0);
        l.vertical = false;

        lines.push_back(l);

        int minY = l.from.y, maxY = l.from.y;
        int minX = l.from.x, maxX = l.to.x;
        // debug(maxX);

        Point st = l.from, rt = l.to;
        // s rotate around r

        //debug(lines.size());
        _for(i, 0, n) {
            int sz = lines.size();
            _for(j, 0, sz) {
                Line nl = lines[j].rot(rt);
                nl.normalize();
                lines.push_back(nl);
                // debug(lines.size());
            }
            rt = rotate(st, rt);
        }

        // rotate finished

        map<Point, char> mp;
        _for(i, 0, lines.size()) {
            Point& lp = lines[i].from;
            lp.x *= 2;
            if(lines[i].vertical) lp.x--;

            minX = min(minX, lp.x);
            maxX = max(maxX, lp.x);
            minY = min(minY, lp.y);
            maxY = max(maxY, lp.y);

            //debug(maxY);
            //debug(maxX);

            mp[lp] = lines[i].vertical ? '|' : '_';
        }

        // output
        // debug(minX);
        string buf;
        _forDown(y, maxY, minY) {
            buf.clear();
            _rep(x, minX, maxX) {
                Point cur(x, y);
                if(mp.count(cur)) buf += mp[cur];
                else buf += ' ';
            }
            while(*(buf.rbegin()) == ' ') buf.erase(buf.size() - 1);
            cout << buf << endl;
        }
        cout << '^' << endl;
    }
}

求最小操作次数

LA6152

LA6152

string S, T;
int diff[2][2];

void init() {
    Set(diff, 0);
}

int solve() {
    int q0 = 0, q1 = 0;
    int ans = 0;

    _for(i, 0, S.size()) if(S[i] != T[i]) {
        if(S[i] == '0') diff[0][1]++;
        if(S[i] == '1') diff[1][0]++;
        if(S[i] == '?' && T[i] == '0') q0++;
        if(S[i] == '?' && T[i] == '1') q1++;
    }

    int x = min(diff[0][1], diff[1][0]);
    ans = x + q0;
    diff[0][1] -= x;
    diff[1][0] -= x;

    if(diff[1][0] > q1) return -1;
    ans += diff[1][0] + diff[0][1] + q1;
    return ans;
}

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

    for(int t = 1; cin >> S >> T; t++) {
        init();
        int ans = solve();
        printf("Case %d: %d\n", t, ans);
    }
}

二分思想处理冒泡排序

想办法找到i这个位置应该放置的数
然后 $pos[i] \Rightarrow i$ ，进行归位

LA6588
LA6588

const int maxn = 100000 + 10;
int n, arr[maxn];

vector<pair<int, int> > vec;

void init() {
    Set(arr, 0);
    vec.clear();
}

int Find(int x) {
    _rep(i, 1, n) if(arr[i] == x) return i;
    return -1;
}

void swapSeg(int from, int to) {
    // [from, to]
    int len = to - from + 1;
    _for(i, 0, len / 2) swap(arr[from + i], arr[from + len / 2 + i]);

    vec.push_back(make_pair(from, to));
}

void solve() {
    _rep(i, 1, n) {
        if(arr[i] == i) continue;
        int pos = Find(i);
        int to = i + (pos - i) * 2 - 1;

        while (to > n) {
            int len = pos - i + 1;
            if(len % 2) swapSeg(i + 1, pos);
            else swapSeg(i, pos);

            pos = Find(i);
            to = i + (pos - i) * 2 - 1;
        }
        swapSeg(i, to);
    }
}

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

    while (kase--) {
        init();
        scanf("%d", &n);
        _rep(i, 1, n) scanf("%d", &arr[i]);

        solve();
        printf("%lu\n", vec.size());
        _for(i, 0, vec.size()) printf("%d %d\n", vec[i].first, vec[i].second);
    }
}

环形链表型的冒泡排序

UVA11925

vector<int> cmd, A;
int n;

void init() {
    cmd.clear();
    A.clear();
}

bool ok() {
    _for(i, 0, n) {
        if(A[i] != i + 1) return false;
    }
    return true;
}

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

        int x;
        _for(i, 0, n) {
            scanf("%d", &x);
            A.push_back(x);
        }
        // input finished, then solve

        if(n == 1) {
            puts("");
            continue;
        }

        while(true) {
            if(ok()) break;

            if(A[0] > A[1] && A[0] != n) {
                swap(A[0], A[1]);
                cmd.push_back(1);
            } else {
                A.insert(A.begin(), A[n - 1]);
                A.resize(n);
                cmd.push_back(2);
            }
        }

        _forDown(i, cmd.size() - 1, 0) printf("%d", cmd[i]);
        printf("\n");
    }
}