【第40题】补作业:天津2007省选-路标设置，向上取整搞怪，好不容易才AC

碎碎念

• 本题时2007年天津省选的一道题，二分算法我刷的不多，去年复赛就栽在二分上了。
• 这道题从70分->100->AC，耗费了我不少灵力（老码农在看<<花戎>>，偶尔听见他嘟囔说啥灵力，借来一用本词）。
• 功力还是不够，希望以后能一次AC掉某某题。

题目：P3853 [TJOI2007]路标设置

题目原文请移步下面的链接

• https://www.luogu.com.cn/problem/P3853
  • 参考题解：https://www.luogu.com.cn/problem/solution/P3853
• 标签：OI、二分
• 难度：普及 /提高

题解

思路

• 二分求最优解模版题，当两个已知的路标距离大于mid时，判断两个路标之间需要放几个路标才能保证距离不超过mid
• 下面说一个超级无敌巨坑的点（反正本蒟蒻华丽丽的栽这了，神犇绕道）

70分

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;

void best_coder() {
    int len, n, k;
    cin >> len >> n >> k;
    vector<int> a(n);
    vector<int> b(n);
    cin >> a[0];
    for (int i = 1; i < n;   i) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    int l = 0, r = len;
    int mid = l   ((r - l) >> 1);
    while(l < r && mid > 0) {
        int t = k;
        for(int i = 1; i < n && t >= 0;   i) {
            t -= b[i] / mid;

        }
        if (t >= 0) {
            r = mid - 1;
        } else {
            l = mid   1;
        }
        mid = l   ((r - l) / 2);
    }
    cout << mid;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

100分

• 虽然得分：100，但Subtask #1：RE，问题出在14行代码

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;

void best_coder() {
    int len, n, k;
    cin >> len >> n >> k;
    vector<int> a(n);
    vector<int> b(n);
    cin >> a[0];
    for (int i = 1; i < n;   i) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    int l = 0, r = len;
    int mid = l   r >> 1;
    while(l < r) {
        int t = k;
        for(int i = 1; i < n && t >= 0;   i) {
            t -= (b[i] - 1) / mid;
        }
        if (t >= 0) {
            r = mid;
        } else {
            l = mid   1;
        }
        mid = l   r >> 1;
    }
    cout << mid;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

AC代码

问题14行

代码语言：javascript复制

    int l = 0, r = len;

修改14行，起点改为1

代码语言：javascript复制

int l = 1, r = len;

AC代码

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;

void best_coder() {
    int len, n, k;
    cin >> len >> n >> k;
    vector<int> a(n);
    vector<int> b(n);
    cin >> a[0];
    for (int i = 1; i < n;   i) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    int l = 1, r = len;
    int mid = l   r >> 1;
    while(l < r) {
        int t = k;
        for(int i = 1; i < n && t >= 0;   i) {
            t -= (b[i] - 1) / mid;
        }
        if (t >= 0) {
            r = mid;
        } else {
            l = mid   1;
        }
        mid = l   r >> 1;
    }
    cout << mid;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

END

cin cout int 算法 效率

0 人点赞