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

相关文章

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决