Home Work
描述
临近开学了,大家都忙着收拾行李准备返校,但I_Love_C却不为此担心!
因为他的心思全在暑假作业上:目前为止还未开动(-_-!!还以为他有多冷静呢)。
暑假作业是很多张试卷,我们这些从试卷里爬出来的人都知道,卷子上的题目有选择题、填空题、简答题、证明题等。
而做选择题的好处就在于工作量很少,但又因为选择题题目都普遍很长。
如果有5张试卷,其中4张是选择题,最后一张是填空题,很明显做最后一张所花的时间要比前4张长很多。
但如果你只做了选择题,虽然工作量很少,但表面上看起来也已经做了4/5的作业了。
I_Love_C决定就用这样的方法来蒙混过关。
他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值(按上面的原理,选择题越多价值当然就越高咯)。
现在就请你帮他安排一下,用他仅剩的一点时间来做最有价值的作业。
输入
测试数据包括多组。
每组测试数据以两个整数M,N(1≤M≤20, 1≤N≤10000)开头,分别表示试卷的数目和I_Love_C剩下的时间。
接下来有M行,每行包括两个整数T,V(1≤T≤N,0<V<10000),分别表示做完这张试卷所需的时间以及做完后能得到的价值!
输入以0 0结束。
输出
对应每组测试数据输出I_Love_C能获得的最大价值。
保留小数点2位
样例输入
4 20
4 10
5 22
10 3
1 2
0 0
样例输出
37.00
提示
float的精度可能不够。
你应该使用double类型。
题目来源
ZJGSU
思路分析:
此题是典型的贪心算法故不做过多的解释若不明白者可以去了解下贪心算法。
代码如下:
#include<stdio.h>
int main()
{
int i;
int m,n;
int t[20],v[20];
double s[20];
while(scanf("%d%d",&m,&n)==2&&(m!=0&&n!=0))
{
double vmax=0;
for(i=0;i<m;i++)
scanf("%d%d",&t[i],&v[i]);
for(i=0;i<m;i++)
s[i]=double(v[i])/t[i];
int i1,fag=0;
double max;
while(1)
{
if(fag==m)
break;
max=0;
for(i=0;i<m;i++)
if(s[i]>max)
{
max=s[i];
i1=i;
}
if(t[i1]>n)
{
vmax+=s[i1]*n;
break;
}
else
{
n-=t[i1];
vmax+=v[i1];
s[i1]=0;
fag++;
}
}
printf("%.2lf\n",vmax);
}
return 0;
}
分享到:
相关推荐
Semantic Web Home Work
来自开发商 Leap Fitness Group 的 Home Workout 是一款适合所有人的健身应用程序。 这个应用程式目前已在 iOS 和 Android 平台上发布,完全免费下载。 使用家庭锻炼,您就可以在手掌中拥有一个“私人教练”。 私人...
2022吴的机器学习C1-W2 Home Work:线性回归, 数据文件和应用的包.zip
C语言实现的一道OJ题目,当中运用的算法是贪心算法。
SNR vs. BER Plot Spread Spectrum Modulation, BPSK Signal through AWGN Channel
computer based matlab 1.1章节的code
vicinity of the lower wall of the channel which is enhanced with further increase inWeissenberg number. For shear-thinning bio-fluids (power-law rheological index n 1) greater Weissenberg ...
【项目资源】: 包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。 ... 【项目质量】: 所有源码都经过严格测试,...
Image processing Home work with matlab code inside pdf with detail explanation
java代码-Home Work 0
1、给定可供选择的N,利用M取值[N/e]或[N/e]+1计算M( home_work_01 ) 2、逐个计算P(M),M=1,2,3,…N,通过找出最大值,计算M( home_work_02) 编程规范: http://google.github.io/styleguide/pyguide.html
Java-Home-Work-2.1.1
Java-Home-Work-1.2.2
Home-work
使用per_cpu变量统计统计用户调用内核模块的次数,并在卸载内核模块的时候把所有的cpu上的变量全部累加起来
this is c++ home work code
multimadia computing home work image dithering
Home work of rayleigh and rician fading.
It is a home work of linear system theory. It is a calculation of sine of a matrix.
Home_work03_Solution.ipynb