本文共 2657 字，大约阅读时间需要 8 分钟。

今天学习到了一个非常有趣的思路——“尺取”法。这种方法类似于用尺子来量取物体的长度，通过逐步调整两端点的位置来找到最优解。这种方法在编程中也有广泛的应用，特别是在处理一些需要寻找最大或最小值的问题时。

第一题解析

题目要求给定一个长度为n的01字符串，允许进行m次字符转换（0↔1或1↔0），求最后连续的0或1的最长长度。

解题思路

代码实现

#include 
   
    using namespace std;void solve() {    int n, m;    char s[n];    scanf("%s", s);        int ans = 0;        // 处理连续0的情况    int l = 0, r = 0, cnt = 0;    while (r < n) {        if (s[r] == '0') {            cnt++;            while (cnt > m) {                if (s[l] == '0') {                    cnt--;                }                l++;            }        }        ans = max(ans, r - l + 1);        r++;    }        // 处理连续1的情况    l = 0, r = 0, cnt = 0;    while (r < n) {        if (s[r] == '1') {            cnt++;            while (cnt > m) {                if (s[l] == '1') {                    cnt--;                }                l++;            }        }        ans = max(ans, r - l + 1);        r++;    }        cout << ans << endl;}int main() {    int t;    scanf("%d", &t);    while (t--) {        solve();    }    return 0;}
   

第二题解析

题目要求给定一个n行m列的矩阵，求一个字矩阵，使得这个矩阵的面积最小，且空座位的个数不少于k。

解题思路

代码实现

#include 
   
    #include 
    
     using namespace std;int getsum(int x1, int y1, int x2, int y2) {    return sa[x2][y2] - sa[x2][y1-1] - sa[x1-1][y2] + sa[x1-1][y1-1];}void solve() {    int n, m, k;    char mp[n+1][m+1];    for (int i = 1; i <= n; ++i) {        scanf("%s", mp[i]+1);        for (int j = 1; j <= m; ++j) {            if (mp[i][j] == '.') {                sa[i][j] = sa[i-1][j] + sa[i][j-1] - sa[i-1][j-1];            } else {                sa[i][j] = sa[i-1][j] + sa[i][j-1] - sa[i-1][j-1];            }        }    }        int ans = 0x3f3f3f3f;    for (int i = 1; i <= n; ++i) {        for (int j = i; j <= n; ++j) {            int cc = 1;            for (int kk = 1; kk <= m; ++kk) {                while (cc <= kk && getsum(i, cc, j, kk) >= k) {                    ans = min(ans, (j - i + 1) * (kk - cc + 1));                    cc++;                }            }        }    }        cout << ans << endl;}int main() {    while (true) {        read(n, m, k);        if (n == 0 && m == 0 && k == 0) break;        solve();    }    return 0;}
    
   

总结

通过上述分析和代码实现，我们可以清晰地看到如何利用尺取法解决不同类型的编程问题。这种方法的核心在于通过动态调整两端点，逐步缩小范围，从而找到最优解。

转载地址：http://exaq.baihongyu.com/