【第38题】注意：P1650 田忌赛马,天大的坑题

小码匠

发布于 2023-08-31 14:42:14

1640

发布于 2023-08-31 14:42:14

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

坑点

从本题开始，加【注意】标题的题目需要复习坑点或者知识点

这道题的坑点在条件判断20分->100分，要注意判断顺序、判断顺序、判断顺序

        if (t[lt] > k[lk]) {
            ans += 200;
            ++lt;
            ++lk;
        } else if (t[rt] < k[lk]) {
            ans -= 200;
            --rt;
            ++lk;
        } else if (t[rt] > k[rk]) {
            --rt;
            --rk;
            ans += 200;
        } else if (t[rt] == k[lk]) {
            --rt;
            ++lk;
        }

题目：P1650 田忌赛马

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

https://www.luogu.com.cn/problem/P1650
- 参考题解：https://www.luogu.com.cn/problem/solution/P1650
标签：OI、贪心
难度：普及+/提高

题解

思路

当田忌当前最快的马比齐王当前最快的马要快时直接拿200银子
如果不行，此时要考虑一个优先级：是直接用最慢的生怼，还是判断最后一匹马能否带来收益（说多了都是泪啊）
- 当田忌最慢的马比齐王最慢的马快时，那这匹马可以为田忌带来200银子
- 反之，怎样都赚不到钱的情况下直接怼就行了，耗费齐王的好马
划重点！！！一定要先判断最慢的马能否带来收益，要不然就是华丽丽的20分WA等着你

20分代码

#include <bits/stdc++.h>

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

void best_coder() {
    int n, rt, rk, lt, lk;
    cin >> n;
    vector<int> k(n);
    vector<int> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }
    sort(t.begin(), t.end(), greater<int>());
    sort(k.begin(), k.end(), greater<int>());
    long long ans = 0;
    rt = n - 1;
    rk = n - 1;
    lk = 0;
    lt = 0;
    for (int i = 0; i < n; ++i) {
        if (t[lt] > k[lk]) {
            ans += 200;
            ++lt;
            ++lk;
        } else if (t[rt] < k[lk]) {
            ans -= 200;
            --rt;
            ++lk;
        } else if (t[rt] > k[rk]) {
            --rt;
            --rk;
            ans += 200;
        } else if (t[rt] == k[lk]) {
            --rt;
            ++lk;
        }
    }
    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 best_coder() {
    int n, rt, rk, lt, lk;
    cin >> n;
    vector<int> k(n);
    vector<int> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }
    sort(t.begin(), t.end(), greater<int>());
    sort(k.begin(), k.end(), greater<int>());
    long long ans = 0;
    rt = n - 1;
    rk = n - 1;
    lk = 0;
    lt = 0;
    for (int i = 0; i < n; ++i) {
        if (t[lt] > k[lk]) {
            ans += 200;
            ++lt;
            ++lk;
        } else if (t[rt] > k[rk]) {
            --rt;
            --rk;
            ans += 200;
        } else if (t[rt] < k[lk]) {
            ans -= 200;
            --rt;
            ++lk;
        } else if (t[rt] == k[lk]) {
            --rt;
            ++lk;
        }
    }
    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;
}

END

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

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

cin