jzoj 1285_奶酪厂_贪心

lzusa 发布于 2020-08-20 3 次阅读


##题目描述
奶牛买了一个奶酪厂生产奶酪,已知每周生产一单位奶酪的费用为C_i,每周可以生产任意数量的奶酪,现在要为接下来N(1<=N<=10,000)周做生产计划。
  厂里有一个仓库,存储量无穷大,可以用来存储暂时不用的奶酪,每单位奶酪每周花费S(1<=S<=100)。
  告诉你每周客户的需求量Y_i(0<=Y_i<=10,000),请你帮忙用最少的钱满足这些需求。


##思路
贪心,显然可以记录一个值min,如果这个值加上S < 当前的费用c[i],那么就可以直接用以前剩下的就可以了
否则将其替换


#include <stdio.h>
#define min(x, y) (x) < (y) ? (x) : (y)
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    long long ans = 0, minn = 0x7f7f7f7f;
    for (int i = 1; i <= n; i++)
    {
        int x, w;
        scanf("%d%d", &w, &x);
        minn = min(minn + m, w);
        ans += minn * x;
    }
    printf("%lld\n", ans);
}