【寒假任務(wù)】洛谷1208 [USACO1.3]混合牛奶 Mixing Milk

2019-11-14 12:05:37

字體：大中小

供稿：網(wǎng)友

問題描述 由于乳制品產(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 行共二個數(shù)值:N,(0<=N<=2,000,000)是需要牛奶的總數(shù)；M,(0<= M<=5,000)是提供牛奶的農(nóng)民個數(shù)。第 2 到 M+1 行:每行二個整數(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ú)的一個整數(shù)，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小費(fèi)用。 樣例輸入 100 5 5 20 9 40 3 10 8 80 6 30 樣例輸出 630 算法討論 比較典型的部分背包問題，用貪心即可。

const maxn=5000;var w,c:array[1..maxn] of longint; i,j,n,m:longint; s:int64;PRocedure qsort(l,r:longint);var i,j,t,m:longint;begin i:=l; j:=r; m:=w[(l+r) div 2]; repeat while w[i]<m do inc(i); while w[j]>m do dec(j); if i<=j then begin t:=w[i]; w[i]:=w[j]; w[j]:=t; t:=c[i]; c[i]:=c[j]; c[j]:=t; inc(i); dec(j) end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r)end;begin read(n,m); for i:=1 to m do read(w[i],c[i]); qsort(1,m); i:=1; repeat if c[i]<=n then begin dec(n,c[i]); inc(s,w[i]*c[i]); inc(i) end else begin inc(s,w[i]*n); n:=0 end; until n=0; write(s)end.

這里寫圖片描述遲到的生日祝福，拉姆雷姆生日快樂！ Pixiv ID：61240729