洛谷P1090(C++结构体排序) / HDU1009(JAVA版结构体排序)

2024-01-09 00:58

本文主要是介绍洛谷P1090(C++结构体排序) / HDU1009(JAVA版结构体排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

/*P1090 合并果子
题目描述
在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。


每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n-1n−1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。


因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11 ,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。


例如有 33 种果子,数目依次为 11 , 22 , 99 。可以先将 11 、 22 堆合并,新堆数目为 33 ,耗费体力为 33 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 1212 ,耗费体力为 1212 。所以多多总共耗费体力 =3+12=15=3+12=15 。可以证明 1515 为最小的体力耗费值。*/

#include<iostream>
#include<algorithm>
using namespace std;
int main()                         //典型的贪心,每一次都只合并所花力气最小的两堆果子!
{
int a[10000], n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);             //初始排序
for (;;)
{
int j = 1;
if (j == n)              
break;
else
{
a[j] += a[j + 1];
sum += a[j];
for (int i = j + 1; i < n; i++)    //将第一堆后面的前移一个位置,去掉最后一堆
{
a[i] = a[i + 1];
}
n--;
for (int i = j; i < n; i++)        //把果子堆重新再从小到大排序继续循环直至跳出!
{
if (a[i] > a[i + 1])
swap(a[i], a[i + 1]);
}
}
}
cout << sum << endl;
return 0;
}

 

HDU1009 FatMouse' Trade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 95024    Accepted Submission(s): 33121

Problem 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

 也是明显的结构体排序,按性价比高低排序,贪心优先选择性价比高的。

但是JAVA中是用类实现结构体,并且要写出按条件排序的方法。

import java.util.*;class node implements Comparable
{public int bean;      //成员变量public int food;public double x;node(int n,int m,double s)   //初始构造方法{this.bean=n;this.food=m;this.x=s;}public int compareTo(Object o) {   //排序比较的方法,根据x按降序排列node n=(node)o;if(x>n.x)return -1;else if(x<n.x)return 1;elsereturn 0;}
}public class Main {public static void main(String[] args){Scanner sc=new Scanner(System.in);int m,n;node[] box=new node[1001];while(sc.hasNext()) {double ans=0;m=sc.nextInt();n=sc.nextInt();if(m==-1&&n==-1)break;for(int i=1;i<=n;i++){int a,b;a=sc.nextInt();b=sc.nextInt();box[i]=new node(a,b,(double)a/(double)b);}Arrays.sort(box,1,n+1);              //用Arrays.sort完成排序for(int i=1;i<=n;i++){               //贪心选取的过程if(m>box[i].food){ans+=(double)box[i].bean;m-=box[i].food;}else{ans+=(((double)m*(double)box[i].bean)/(double)box[i].food);break;}}System.out.println(String.format("%.3f", ans));}}
}

 

对于JAVA来说arrays.sort()函数默认是从小到大排列的,如果想从大到小排序,也可以通过重写compare函数来实现:

Comparator<Integer> cmp = new Comparator<Integer>() {public int compare(Integer i1, Integer i2) {return i2-i1;}};
Arrays.sort(arr, cmp);

注意在此中arr类型只能为Integer或者Double,如果数组是int或double类型则必须修改为它的包装类如Integer才能使用!

这篇关于洛谷P1090(C++结构体排序) / HDU1009(JAVA版结构体排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数