【第32题】一步之遥之USACO杠上奶牛

[USACO18JAN]Rental Service S

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

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

思路

• 判断每头奶牛是卖奶还是租给邻居划算，值得注意的是，当这个商店所需奶的数量满足，但还有剩余的奶时，剩下的奶可以继续卖给其他商店，而所得的钱都算这一头奶牛赚来的，不能分开算。最后将卖给商店的钱和邻居给的钱放在一起比较大小，求前n个值相加即可

代码：爆零

• 测试快结束时，把第一道题代码给提交，覆盖了原来的分数，直接爆零。

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

void coder() {
	int n;
    cin >> n;
    for (int i = 0; i < n;   i) {
    	int a;
    	cin >> a;
	}
	cout << 2970;
}
int main() {
    coder();
    return 0;
}

代码：20分

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

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

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

代码：AC

只改了一行代码，上面代码26行

代码语言：javascript复制

while (v[i] > 0) {

改成

代码语言：javascript复制

 while (v[i] > 0 && j >= 0) {

AC代码

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

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

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

END

int scanf sort 测试 排序

0 人点赞