首页 > 代码库 > HDU 4803 Poor Warehouse Keeper(贪心)
HDU 4803 Poor Warehouse Keeper(贪心)
题目链接
题意 ：屏幕可以显示两个值，一个是数量x，一个是总价y。有两种操作，一种是加一次总价，变成x，1+y；一种是加一个数量，这要的话总价也会相应加上一个的价钱，变成x+1，y+y/x。总价显示的为取整后的整数，小数部分忽略。给定一个目标x，y，初始状态为1，1，求最少需要多少次可以目标状态，不可以达到的话输出-1.
思路 ：如果是加一次总价的话，单价就在变大；如果是加一次数量的话，单价是不变的。因此，单价只涨不降。物品的数量也必须从1变成x，也就是说至少要加x-1次单价才可以，那么如果单价过大s，s*(x+1)≥y+1肯定是不予许的。所以对于每一个i(数量)来说，单价都有一个上限值，以保证说在增加数量的时候不会导致总价溢出。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 5 using namespace std ; 6 7 const double eps = 1e-9; 8 int main() 9 {10 double x ,y ;11 while(~scanf("%lf %lf",&x,&y)) {12 if(x > y)13 {14 printf("-1\n") ;15 continue ;16 }17 double price = (y+1-eps)/x ;//以最终的题目中要求的两个数x，y来算，最终单价应该是s18 double sum = 1.0 ;19 int ans = int(x-1) ;//数量变的话，总价是不会变的，所以要变到最终的x，至少也要变x-1次20 for(int i = 1 ; i <= int(x) ; i++){21 double totalprice = i*price ;//以price为最终单价，那么以现在的数量应该拥有的总价是多少22 int k = (int)(totalprice-sum) ;//还差多少到以该单价到达的总价23 ans += k ;//加上相差的那些24 sum += k ;//增长数量的时候总价也是增长的25 sum = sum * ((i+1)*1.0/i) ;26 }27 printf("%d\n",ans) ;28 }29 return 0 ;30 }
HDU 4803 Poor Warehouse Keeper(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。