发表于   |   分类于 洛谷 , 刷题   |   暂无评论

url: https://www.luogu.com.cn/problem/P1281

tag：
二分，贪心

思路：
求可以满足条件的最小值，所以可以想到用二分来做。二分的是复制时间，所以范围是在0到全部的页数。二分的思路是利用这个复制时间来求出一个需要的人数，将这个人数和题目所给的认识做一个比较，因为要满足条件，所以人数需要小于等于题目给的人数。可以知道如果复制时间越大，表示一个人可以抄的书越多，需要的人数越少，所以人数和复制时间是单调递减的关系。利用这个单调递减的关系，可以二分出一个复制时间，使得这个复制时间是当所需人数小于等于所需人数时，复制时间最小。然后就可以通过这个复制时间来求出每一个人所抄的书的起始范围。因为要求是让前面的人尽可能的少抄，所以就需要让后面的人多抄，因此再输出答案的时候用到了贪心的思想，从后往前遍历书，使得每次每个人都尽可能抄多一点的书，通过这种遍历方式实现题目要求的让前面的人尽可能少抄。在二分的时候也有用到这种遍历方式，但是后面写题解的时候觉得或许二分的时候不需要，因为只是求一个人数，没有前后之分。

代码：

#include <iostream>
using namespace std;
int m, k;
const int N = 550;
int a[N];
int x[N], y[N];
bool check(int x)
{
    int now = 1;
    int cnt = 0;
    for (int i = m - 1; i >= 0; i --)
    {
        if (cnt + a[i] > x)
        {
            cnt = 0;
            now ++;
        }
        cnt += a[i];
    }
    return now <= k;
}
int main()
{
    cin >> m >> k;
    int kk = k;
    int l = 0, r = 0;
    for (int i = 0; i < m; i ++)
    {
        cin >> a[i];
        r += a[i];
    }
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    int t = 0;
    y[k] = m; x[1] = 1;
    for (int i = m - 1; i >= 0; i --)
    {
        if (t + a[i] > l)
        {
            t = 0;
            x[k] = i + 2;
            y[--k] = i + 1;
        }
        t += a[i];
    }
    for (int i = 1; i <= kk; i ++)
    {
        cout << x[i] << ' ' << y[i] << '\n';
    }
    return 0;
}

发表于   |   分类于 洛谷 , 刷题   |   暂无评论

url: https://www.luogu.com.cn/problem/P1827

tag:
递归， 二叉树

代码：

#include <iostream>
#include <string>
using namespace std;

string inorder, preorder;

void buildPostorder(int inStart, int inEnd, int preStart, int preEnd) {
    // 若范围无效，则返回
    if (inStart > inEnd || preStart > preEnd) {
        return;
    }

    // 前序遍历的第一个元素即为根节点
    char root = preorder[preStart];

    // 在中序遍历中找到根节点的位置
    int rootIndex = -1;
    for (int i = inStart; i <= inEnd; ++i) {
        if (inorder[i] == root) {
            rootIndex = i;
            break;
        }
    }

    // 根节点左边的节点个数
    int leftTreeSize = rootIndex - inStart;

    // 递归处理左子树
    buildPostorder(inStart, rootIndex - 1,
                   preStart + 1, preStart + leftTreeSize);

    // 递归处理右子树
    buildPostorder(rootIndex + 1, inEnd,
                   preStart + leftTreeSize + 1, preEnd);

    // 最后输出根节点，实现后序遍历顺序：左子树 -> 右子树 -> 根
    cout << root;
}

int main() {
    // 输入中序遍历和前序遍历字符串
    cin >> inorder >> preorder;

    int n = inorder.size();
    buildPostorder(0, n - 1, 0, n - 1);

    return 0;
}

发表于   |   分类于 生活   |   暂无评论

今天是把网盘程序onemanager搬过来了，然后还把两个自己写的网站一个是订阅服务，另外一个是链接网盘都搬过来了。
顺便把之前搭的另外一个博客删掉了，因为主要都是黑历史，然后没有写几篇文章。
突然感觉还是php写的博客程序好，搬家很方便，不用再写反向代理，然后再设置nginx的配置，就很方便。