【第31题】一步之遥之不要走弯路

小码匠

发布于 2023-08-31 14:30:15

1620

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

P6023 走路

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

https://www.luogu.com.cn/problem/P6023
- 参考题解：https://www.luogu.com.cn/problem/solution/P6023
标签：贪心

思路

贪心思想，很明显，把所有天数放在一天是最优情况。枚举每一天的分数，然后进行比较即可

代码：爆零

#include <bits/stdc++.h>

using namespace std;

void coder() {
    long long n;
    int m, k;
    scanf("%lld%d%d", &n, &m, &k);
    vector<pair<long long, long long> > v(k);
    for (int i = 0; i < k; ++i) {
        scanf("%lld%lld", &v[i].first, &v[i].second);
    }
    sort(v.begin(), v.end());
    long long a = 0;
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        if (v[i].first > a) {
            a = v[i].first;
            long long t = 1;
            long long temp = 0;
            for (int j = i + 1; v[j].second < n; ++j, ++i) {
                temp += t * (v[j].second - v[j - 1].second);
                ++t;
            }
            temp += t * (n - v[i].second);
            ans = max(ans, temp);
        }
    }
    cout << ans;
}

int main() {
    coder();
    return 0;
}

代码：AC

只改了一行爆零代码，第21行代码

for (int j = i + 1; v[j].second < n; ++j, ++i) {

改成

for (int j = i + 1; v[j].second < n && v[j].first == a; ++j, ++i) {

AC代码

#include <bits/stdc++.h>

using namespace std;

void coder() {
    long long n;
    int m, k;
    scanf("%lld%d%d", &n, &m, &k);
    vector<pair<long long, long long> > v(k);
    for (int i = 0; i < k; ++i) {
        scanf("%lld%lld", &v[i].first, &v[i].second);
    }
    sort(v.begin(), v.end());
    long long a = 0;
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        if (v[i].first > a) {
            a = v[i].first;
            long long t = 1;
            long long temp = 0;
            for (int j = i + 1; v[j].second < n && v[j].first == a; ++j, ++i) {
                temp += t * (v[j].second - v[j - 1].second);
                ++t;
            }
            temp += t * (n - v[i].second);
            ans = max(ans, temp);
        }
    }
    cout << ans;
}

int main() {
    coder();
    return 0;
}

END

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

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

c++