zoj 2109 FatMouse' Trade简单的贪心 (注意double数组的排序问题)

2023-11-08 12:08

本文主要是介绍zoj 2109 FatMouse' Trade简单的贪心 (注意double数组的排序问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2109

1、问题描述

FatMouse' Trade
Time Limit:2000MS    Memory Limit:65536KB    64bit IO Format:%lld & %llu
Submit Status Practice ZOJ 2109

Description

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding   the warehouse containing his favorite food, JavaBean.
  The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and   requires F[i] pounds of cat food. FatMouse does not have to trade for all the   JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he   pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning   this homework to you: tell him the maximum amount of JavaBeans he can obtain.


  Input
 
  The input consists of multiple test cases. Each test case begins with a line   containing two non-negative integers M and N. Then N lines follow, each contains   two non-negative integers J[i] and F[i] respectively. The last test case is   followed by two -1's. All integers are not greater than 1000.


  Output
 
  For each test case, print in a single line a real number accurate up to 3 decimal   places, which is the maximum amount of JavaBeans that FatMouse can obtain.


  Sample Input

 
  5 3
  7 2
  4 3
  5 2
  20 3
  25 18
  24 15
  15 10
  -1 -1


  Sample Output
 
  13.333
  31.500


 

2、代码:

#include<stdio.h>
#include<stdlib.h>
struct node
{double j,f;double p;
}a[1010];
int cmp(const void *a,const void *b)
{struct node *c=(node *)a;struct node *d=(node *)b;if(c->p > d->p) return -1;else return 1;
}
int main()
{int N;double M;double ans;while(scanf("%lf%d",&M,&N)){if(M==-1&&N==-1) break;for(int i=0;i<N;i++){scanf("%lf%lf",&a[i].j,&a[i].f);a[i].p=a[i].j/a[i].f;}qsort(a,N,sizeof(a[0]),cmp);ans=0;for(int i=0;i<N;i++){if(M>=a[i].f){ans+=a[i].j;M-=a[i].f;}else{ans+=(a[i].j/a[i].f)*M;break;}}printf("%.3lf\n",ans);}return 0;
}


 

这篇关于zoj 2109 FatMouse' Trade简单的贪心 (注意double数组的排序问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369746

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.