bLue祝你元宵節(jié)快樂(lè)！（貪心）

2019-11-08 03:06:27

字體：大中小

供稿：網(wǎng)友

PRoblem Description

元宵節(jié)到了，bLue 從超市采購(gòu)了 n 種湯圓準(zhǔn)備好好享受一下。

他買(mǎi)回來(lái)的 n 種湯圓，每種都有 3 個(gè)屬性：?jiǎn)蝹€(gè)湯圓能提供的愉悅值 a、購(gòu)買(mǎi)數(shù)量 b、每碗最多可以容納湯圓的個(gè)數(shù) c。

不過(guò)，bLue 的飲食習(xí)慣略奇特，他的飯量可以一次吃 m 碗湯圓，但是每碗的湯圓必須全部是同一種湯圓且必須裝滿(mǎn)一碗（即湯圓個(gè)數(shù)等于此類(lèi)湯圓的最大容納量 c），否則他就不會(huì)吃。

那么問(wèn)題來(lái)了，bLue 應(yīng)該如何下這 m 碗湯圓，才能使他獲得的總愉悅值最高？ Input

輸入數(shù)據(jù)有多組（數(shù)據(jù)組數(shù)不超過(guò) 100），到 EOF 結(jié)束。

對(duì)于每組數(shù)據(jù)：

第 1 行包含 2 個(gè)整數(shù) n, m (1 <= n, m <= 100)，表示湯圓種類(lèi)數(shù)和 bLue 最多能吃的碗數(shù)。第 2 行包含 n 個(gè)用空格隔開(kāi)的整數(shù) ai (0 <= ai <= 100)，表示每種湯圓的單個(gè)可獲得的愉悅值。第 3 行包含 n 個(gè)用空格隔開(kāi)的整數(shù) bi (0 <= bi <= 100)，表示每種湯圓的購(gòu)買(mǎi)數(shù)量。第 4 行包含 n 個(gè)用空格隔開(kāi)的整數(shù) ci (1 <= ci <= 100)，表示每種湯圓的在一碗內(nèi)的最大容納量。

Output

對(duì)于每組數(shù)據(jù)，輸出 1 行，包含 1 個(gè)整數(shù)，表示 bLue 能獲得的最大愉悅值。 Example Input

3 3 1 2 3 5 4 2 2 2 3 2 5 4 1 2 0 1 1

Example Output

10 8

#include <stdio.h>#include <string.h>#define N 105struct node{ int value; int num;}id[N],t;int main(){ int n,m,i,j,sum; int a[N],b[N],c[N]; while(~scanf("%d%d",&n,&m)) { int i; sum=0; for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) scanf("%d",&b[i]); for(i=0;i<n;i++) scanf("%d",&c[i]); for(i=0;i<n;i++) { id[i].value=a[i]*c[i]; id[i].num=b[i]/c[i]; } for (i = 0; i < n; ++i) { for (j = 0; j <n-i-1; ++j) { if(id[j].value<id[j+1].value) { t=id[j]; id[j]=id[j+1]; id[j+1]=t; } } } for(i=0;i<n;i++) { if(id[i].num<m) { m-=id[i].num; sum+=id[i].value*id[i].num; } else { sum+=id[i].value*m; break; } } printf("%d/n",sum ); } return 0;}

上一篇：筆試題（帶答案）

下一篇：JS工具類(lèi)