【第60题】还账，九牛二虎之力AC掉 [NOIP2018 普及组] 龙虎斗

小码匠

发布于 2023-08-31 15:06:44

1650

发布于 2023-08-31 15:06:44

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

碎碎念

这道题2022年8月第一次做，没AC掉，只得了72分；
虽然是道普及-, 今天也是废了九牛二虎之力才AC掉的，题解中第3点是我今后写代码要注意的。

题目： [NOIP2018 普及组] 龙虎斗

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

https://www.luogu.com.cn/problem/P5016
- 参考题解：https://www.luogu.com.cn/problem/solution/P5016
标签：OI、 NOIP、模拟、枚举
难度：普及-

题解

先判断哪一方现有的多（别忘加后补的），然后通过用二者所差数除以s2再乘上s2来算在哪个位置能使二者数据更接近，如果本来就一样那就输出m就行
这里有一个坑点就是算出来的位置可能越界，所以一定要进行判断
判断条件写太长容易把自己绕进去，很容易导致最后判断出现错误，最好避免！！！

思路

题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P5016

代码：88分

头次遇到这么吉利的分数，但我要AC啊，我不要这个吉利数！

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';
typedef long long LL;

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    LL n, m, p1, s1, s2;
    cin >> n;
    vector<LL> v(n + 1);
    for (LL i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    cin >> m >> p1 >> s1 >> s2;
    LL a = 0, b = 0;
    for (LL i = 1; i < m; ++i) {
        a += v[i] * (m - i);
    }
    for (LL i = m + 1; i <= n; i++) {
        b += v[i] * (i - m);
    }
    if (p1 <= m - 1)  {
        a += s1 * (m - p1);
    }
    if (p1 >= m + 1) {
        b += s1 * (p1 - m);
    }
    if (a == b) {
        printf("%lld", m);
        return;
    }
    LL t = 0;
    if (abs(a - b) - abs(a - b) / s2 * s2 > abs(a - b) / s2 * s2 + s2 - abs(a - b)) {
        ++t;
    }
    if (a < b) {
        long long one = 1;
        cout << max(one,  m - abs(a - b) / s2);
    }
    else if (a > b) {
        cout << min(n, m + abs(a - b) / s2 + t);
    }
}

void happy_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main() {
    // 小码匠
    best_coder();

    // 最优解
    //happy_coder();
    return 0;
}

AC代码

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';
typedef long long LL;

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    LL n, m, p1, s1, s2;
    cin >> n;
    vector<LL> v(n + 1);
    for (LL i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    cin >> m >> p1 >> s1 >> s2;
    LL a = 0, b = 0;
    for (LL i = 1; i < m; ++i) {
        a += v[i] * (m - i);
    }
    for (LL i = m + 1; i <= n; i++) {
        b += v[i] * (i - m);
    }
    if (p1 <= m - 1) {
        a += s1 * (m - p1);
    }
    if (p1 >= m + 1) {
        b += s1 * (p1 - m);
    }
    if (a == b) {
        cout << m;
        return;
    }
    LL l = abs(a - b);
    LL t = l / s2;
    LL cnt = t * s2;
    if (l - cnt > cnt + s2 - l) {
        ++t;
    }

    if (a < b) {
        long long one = 1;
        cout << max(one, m - t);
    } else if (a > b) {
        cout << min(n, m + t);
    }
}

void happy_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main() {
    // 小码匠
    best_coder();

    // 最优解
    //happy_coder();
    return 0;
}

END

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

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

cin