【第30题】严禁用double，我用了，咋的[USACO14JAN]Bessie Slows Down S

小码匠

发布于 2023-08-31 14:29:49

2490

发布于 2023-08-31 14:29:49

文章被收录于专栏：小码匠和老码农

精度问题

老码农说，做项目时，尤其涉及钱的场景，计算时很容易发生精度问题，你多给了客户，客户自己欢天喜地，但公司亏了，你少給客户，能绕得了你吗？

他们之前做项目时，绝大部分场严禁用`double`、`float`，一旦Code review或者代码质量扫描到，该同学就会被吊打！

反正我这次用`double`，总不能也吊打我吧。

[USACO14JAN]Bessie Slows Down S

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

https://www.luogu.com.cn/problem/P2338
- 参考题解：https://www.luogu.com.cn/problem/solution/P2338
标签：模拟、贪心、线性结构

思路

因为每秒走1/(k + 1)米，所以当不考虑精度问题，只卡数据正好是整数的情况（如样例）时，可以得到每米需要k+1秒，然后按米模拟，这种方法局限性很强，最后得到的值正常情况下都会比正确答案大
而正解则考虑了精度，按照犯错的时间去求走过的长度，判断按时间和按路程哪个错误在前，最后在加上最后一个错误到终点所需的时间

代码：20分

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

void best_coder() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> t;
    priority_queue<int, vector<int>, greater<int>> d;
    for (int i = 0; i < n; ++i) {
        char c;
        int m;
        cin >> c >> m;
        if (c == 'T'){
            t.push(m);
        } else {
            d.push(m);
        }
    }
    long long ans = 0;
    long long v = 1;
    for (int i = 1; i <= 1000; ++i) {
        ans += v;
        if (!t.empty() && ans >= t.top()) {
            ++v;
            t.pop();
        }
        if (!d.empty() && i == d.top()) {
            ++v;
            d.pop();
        }
    }
    cout << ans;
}

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

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

void happy_coder() {
    int n;
    cin >> n;
    priority_queue<double, vector<double>, greater<double>> t;
    priority_queue<double, vector<double>, greater<double>> d;
    for (int i = 0; i < n; ++i) {
        char c;
        double m;
        cin >> c >> m;
        if (c == 'T'){
            t.push(m);
        } else {
            d.push(m);
        }
    }
    double v, ans = 0, s = 1.0, len = 0,  tl, dl;
    while (!t.empty() || !d.empty()) {
        v = 1.0 / s;

        if (t.empty()) {
            tl = 0x3f3f3f3f;
            dl = d.top();
        } else if (d.empty()) {
            dl = 0x3f3f3f3f;
            tl = len + (t.top() - ans) * v;
        } else {
            tl = len + (t.top() - ans) * v;
            dl = d.top();
        }
        if (tl < dl) {
            len = tl;
            ans = t.top();
            t.pop();
        } else {
            ans += (dl - len) / v;
            len = dl;
            d.pop();
        }
        ++s;
    }
    ans += (1000 - len) / (1.0 / s);
    cout << int(ans + 0.5);
}

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

    // 小码匠
    //best_coder();

    // 最优解
    happy_coder();

    // 返回
    return 0;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除

double