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

P6023 走路

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

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

思路

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

代码：爆零

代码语言：javascript复制

#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行代码

代码语言：javascript复制

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

改成

代码语言：javascript复制

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

AC代码

代码语言：javascript复制

#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

c++ int max scanf std

0 人点赞