題目描述由于乳制品產(chǎn)業(yè)利潤很低，所以降低原材料（牛奶）價(jià)格就變得十分重要。幫助Marry乳業(yè)找到最優(yōu)的牛奶采購方案。Marry乳業(yè)從一些奶農(nóng)手中采購牛奶，并且每一位奶農(nóng)為乳制品加工企業(yè)提供的價(jià)格是不同的。此外，就像每頭奶牛每天只能擠出固定數(shù)量的奶，每位奶農(nóng)每天能提供的牛奶數(shù)量是一定的。每天Marry乳業(yè)可以從奶農(nóng)手中采購到小于或者等于奶農(nóng)最大產(chǎn)量的整數(shù)數(shù)量的牛奶。給出Marry乳業(yè)每天對牛奶的需求量，還有每位奶農(nóng)提供的牛奶單價(jià)和產(chǎn)量。計(jì)算采購足夠數(shù)量的牛奶所需的最小花費(fèi)。注：每天所有奶農(nóng)的總產(chǎn)量大于Marry乳業(yè)的需求量。輸入輸出格式輸入格式：第 1 行共二個(gè)數(shù)值:N,(0<=N<=2,000,000)是需要牛奶的總數(shù)；M,(0<= M<=5,000)是提供牛奶的農(nóng)民個(gè)數(shù)。第 2 到 M+1 行:每行二個(gè)整數(shù):Pi 和 Ai。Pi(0<= Pi<=1,000) 是農(nóng)民 i 的牛奶的單價(jià)。Ai(0 <= Ai <= 2,000,000)是農(nóng)民 i 一天能賣給Marry的牛奶制造公司的牛奶數(shù)量。輸出格式：單獨(dú)的一行包含單獨(dú)的一個(gè)整數(shù)，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小費(fèi)用。輸入輸出樣例輸入樣例#1：100 55 209 403 108 806 30輸出樣例#1：630題解：這道題用貪心，f[i]表示單價(jià)為i的牛奶的產(chǎn)量，這樣就可以節(jié)省排序的時(shí)間。var f:array[0..1001]of longint; i,n,m,ans,a,b:longint;begin fillchar(f,sizeof(f),0); readln(m,n); for i:=1 to n do begin readln(a,b); f[a]:=f[a]+b; end; ans:=0; for i:=0 to 1000 do if m>f[i] then begin ans:=ans+f[i]*i;m:=m-f[i]; end else begin ans:=ans+m*i; break; end; write(ans);end.
