原題:
http://172.16.0.132/senior/#contest/show/2061/0
題目描述:
奶牛買了一個奶酪廠生產奶酪,已知每周生產一單位奶酪的費用為C_i锉屈,每周可以生產任意數(shù)量的奶酪脾歇,現(xiàn)在要為接下來N(1<=N<=10,000)周做生產計劃报破。
廠里有一個倉庫,存儲量無窮大站叼,可以用來存儲暫時不用的奶酪,每單位奶酪每周花費S(1<=S<=100)菇民。
告訴你每周客戶的需求量Y_i(0<=Y_i<=10,000)尽楔,請你幫忙用最少的錢滿足這些需求投储。
輸入:
第1行:兩個空格隔開的整數(shù)N,S
第2-N+1行:每行兩個空格隔開的整數(shù)C_i和Y_i。
輸出:
輸出一個整數(shù)表示最少花費阔馋。注意答案可能會超出longint范圍玛荞。
樣例輸入:
4 5
88 200
89 400
97 300
91 500
樣例輸出:
126900
樣例說明:
第一周生產200單位,第二周生產700單位呕寝,400給客戶勋眯,300存在倉庫里留給第三周,第四周生產500單位壁涎。
分析:
lj貪心
對于每一周凡恍,只可能是至一周制作或由上幾周留下來的,那么我們取這兩個數(shù)的最小值就是費用
實現(xiàn):
#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);
}