题目链接: 酷丁编程:1283
1283 [安徽省赛小学组 2011 第2题] 最高得分(maxvalue)
经验值:1200
时间限制:1000毫秒
内存限制:128MB
安徽省2011年信息学竞赛试题(小学组)
不许抄袭,一旦发现,直接清空经验!
题目描述 De**ion
三次方求和的问题,被卡卡西迎刃而解,芭比阿姨拿出钥匙,打开了她后花园的大门。卡卡西被眼前的景色惊呆了!她从未见过这么多珍奇的鲜花,还有她梦寐以求的在阳光下发出异样光彩的水晶珠,她慢慢向前走着,忽然被一小块花圃吸引住了。这块花圃中,满是各式各样闪闪发亮的字母水晶珠,卡卡西心想要是能从这花圃中取出自己想要的字母水晶珠串成项链,那该多好啊!卡卡西往右手边一看,有一个告示牌,上面写道:亲爱的朋友,如果你想从花圃中获取字母水晶珠,必须先完成如下游戏:假设所有的字母水晶珠都可以采,每种字母水晶珠的单颗价值都是一样的,且采摘任意一颗水晶珠所需要的时间都是1秒,但是采摘水晶珠的总时间是有限的,那么应该如何选择自己所要的字母水晶珠,使得总价值最高呢?假设每种字母水晶珠的数量和总价值用(A,B)表示,其中A表示这种水晶珠总的数量,B表示所有这种水晶珠的总价值。例如一共有3种字母水晶珠,其数量和价值分别如下:(4,20)、(4,24)、(5,38),留给卡卡西采摘水晶珠的总时间是10秒,则选择后两种水晶珠全部摘取,第一种摘取一颗时,可得摘取的最大价值为67.00,如果选择摘前两种水晶珠和两颗第三种水晶珠,所能得价值为59.20。小朋友,你能帮助卡卡西计算出给定时间内所能采摘水晶珠的最大价值,从而让她顺利进入花圃采摘字母水晶珠吗?
输入描述 Input De**ion
共N+1行,第一行为两个整数N(100≤N≤10000)和T(1≤T≤10000)(中间用空格隔开),分别表示字母水晶珠种类数和总的采摘时间;后面N行中,每行两个整数S(1≤S≤100)和V(1≤V≤100)(中间用空格隔开),分别表示这种字母水晶珠的总数量和总价值。
输出描述 Output De**ion
一行,所能得到的最大价值,输出结果四舍五入保留两位小数。
样例输入 Sample Input
3 10 4 20 4 24 5 38
样例输出 Sample Output
67.00
数据范围及提示 Data Size & Hint
20%的数据100≤N≤500
60%的数据100≤N≤999
100%的数据100≤N≤10000
代码:
- #include<bits/stdc++.h> using namespace std; int main(){ int n,t,s[10005],v[10005],i,j,k=0; double p[10005],ans=0; cin>>n>>t; for(i=0;i<n;i++){ cin>>s[i]>>v[i]; p[i]=1.0*v[i]/s[i]; } for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if((long long)v[j]*s[j+1]<(long long)v[j+1]*s[j]){ swap(p[j],p[j+1]); swap(s[j],s[j+1]); swap(v[j],v[j+1]); } for(i=0;i<n;i++){ if(k>=t) break; int s1=min(s[i],t-k); ans+=(long long)s1*p[i]; k+=s1; } cout<<fixed<<setprecision(2)<<(double)ans; return 0; }
- 为何只有90分??
发,这样看不懂
