题解SP18965

shaozhehan · 2023-03-26 11:02:51 · 题解

原题链接

SPOJ 链接

题目大意：

有 n 头奶牛在等待挤奶。第 i 个奶牛只能在 t=d(i) 前生产 g(i) 加仑奶。如果时间 t 从 0 开始，那么最多能挤出多少加仑的奶？

思路：

这一题是明显的贪心题目。我们可以把所有奶牛按 g 降序排序，然后拿一个 bool 型数组 vis 来标记时间点是否被占用。接下来，我们遍历一下每一个奶牛，看一看是否有时间点没有被占用。如果有，就把答案加到变量 ans 里，最后输出就行了。

坑点：

• 先输入 g 再输入 d！
• 因为还有时间 d 的限制，我们要把可以挤奶的奶牛尽量往后放。

上代码：

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int d, g;
    bool operator<(const node &x) const {// 重载<运算符，以便排序
        return this->g > x.g;
    }
}nd[10001];

bool vis[10001];

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);// cin、cout 加速
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> nd[i].g >> nd[i].d;// 坑点1
    }
    sort(nd + 1, nd + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = nd[i].d; j >= 1; j--){// 坑点2
            if (!vis[j]){
                vis[j] = true;
                ans += nd[i].g;// 加起来
                break;// 退出循环
            }
        }
    }
    cout << ans << "\n";// 输出
    return 0;
}