Description 情况有点惨不忍睹呀，居然这么多人写贪心？
Luojie学姐想要代码少出bug，所以决定去女装，商店里有n条小裙子每条小裙子的价格和漂亮程度分别为wi和pi，luojie学姐想要k条小裙子，ta希望你能帮ta选出k条小裙子，使得单位价格的漂亮程度最大。
Input
第一行输入n和k(1≤k≤n≤104)，接下来n行为每条小裙子的价格pi和漂亮程度wi(1≤pi≤wi≤106)
Output
单位价格的最大漂亮程度（数据保留到小数点后两位）。
Sample Input
Raw
3 2
2 2
2 8
5 1
Sample Output
Raw
2.50
不会吧，不会吧。看我拿组样例卡死你，
3 2
2 2
5 3
2 1
你贪心的答案就是5/7=0.714,正确答案是0.75.
这题在题库里有一样的题，只不过题面改了下，学长还直播讲过题解。
挑战程序设计上也有题解，
下面放个代码：#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,k; int p[10005],w[10005]; double y[10005]; int pd(double x) { for(int i=0;i<n;i++){ y[i]=w[i]-x*p[i]; } sort(y,y+n); double sum=0; for(int i=0;i<k;i++){ sum+=y[n-1-i]; } if(sum>=0) return 1; else return 0; } int main() { scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d%d",&p[i],&w[i]); double lb=0,rb=10000000; for(int i=0;i<100;i++){ double mid=(lb+rb)/2; if(pd(mid)) lb=mid; else rb=mid; } printf("%.2fn",rb); }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
