2017.07.15【NOIP提高组】模拟赛B组 奶酪厂 题解

原题:

http://172.16.0.132/senior/#contest/show/2061/0

题目描述:

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

输入:

第1行:两个空格隔开的整数N,S
第2-N+1行:每行两个空格隔开的整数C_i和Y_i。

输出:

输出一个整数表示最少花费。注意答案可能会超出longint范围。

样例输入:

4 5
88 200
89 400
97 300
91 500

样例输出:

126900

样例说明:

第一周生产200单位,第二周生产700单位,400给客户,300存在仓库里留给第三周,第四周生产500单位。

分析:

lj贪心
对于每一周,只可能是至一周制作或由上几周留下来的,那么我们取这两个数的最小值就是费用

实现:

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;

int n,m,i;
long long l,c,k,ans;
int main()
{
    scanf("%d%d",&n,&m);
    l=INT_MAX-m;
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&c,&k);
        l=min(l+m,c);
        ans+=l*k;
    }
    printf("%lld",ans);
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容