UVA10026:Shoemaker's Problem(贪心)

时间:2022-09-23 12:53:34

题目链接:  http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68990#problem/K

题目需求:鞋匠有n个任务,第i个任务要花费ti天,同时第i个任务每耽误一天要有fi的罚金。求完成所有任务的最小罚金。

题目解析:

这题看了题解,解法如下:

这个是一个贪心的题目首先按照fine/time降序排列,值相同的再按序号升序排列。

对于为什么贪心策略是这个样子的,我们不妨拿相邻的两个事件a、b来说明一下。由于a、b之后的事件是固定的,所以我们无论排成ab还是排成ba后面部分的损失都是固定的,那么损失的差别主要来源于究竟是排成ab还是排b成a。排ab的损失为ta*fb,排ba的损失为tb*fa,那么如果ta*fb<tb*fa,我们就排成ab,这样可以得到fa/ta>fb/tb,推而广之,就得到了我们的贪心策略。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <queue>
#define eps 1e-9
typedef long long ll;
using namespace std;
struct node
{
int we;
double t,s,z;
}q[];
int n;
int cmp(const void *a,const void *b)
{
struct node *aa=(struct node *)a;
struct node *bb=(struct node *)b;
if(bb->z!=aa->z)
return bb->z>aa->z;
else return aa->we-bb->we;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%lf%lf",&q[i].t,&q[i].s);
q[i].we=i+;
q[i].z=(q[i].s*1.0)/q[i].t;
}
qsort(q,n,sizeof(q[]),cmp);
printf("%d",q[].we);
for(int i=;i<n;i++)
{
printf(" %d",q[i].we);
}
cout<<endl;
if(T!=) cout<<endl;
}
return ;
}

UVA10026:Shoemaker's Problem(贪心)的更多相关文章

  1. UVA-10026 Shoemaker&&num;39&semi;s Problem (贪心)

    题目大意:一个鞋匠,有n只鞋要修,修某只鞋的时间ti已知,某只鞋晚修一天要交的罚款fi也已知.现在让找个修鞋顺序使得罚款最少. 题目分析:本来想水一下这道题,没想到真的AC啦.后来又查的题解,找的解释 ...

  2. UVA 10026 Shoemaker&&num;39&semi;s Problem 鞋匠的难题 贪心&plus;排序

    题意:鞋匠一口气接到了不少生意,但是做鞋需要时间,鞋匠只能一双一双地做,根据协议每笔生意如果拖延了要罚钱. 给出每笔生意需要的天数和每天的罚钱数,求出最小罚钱的排列顺序. 只要按罚款/天数去从大到小排 ...

  3. uva 10026 Shoemaker&&num;39&semi;s Problem&lpar;排序)

    题目连接:10026 Shoemaker's Problem 题目大意:有一个鞋匠接了n双要修的鞋子, 修每双鞋需要d天,每推迟一天修将亏损val元,问按什么样的顺序修鞋可以保证损失最少,如果有多种情 ...

  4. &lpar;贪心5&period;2&period;1&rpar;UVA 10026 Shoemaker&&num;39&semi;s Problem&lpar;利用数据有序化来进行贪心选择&rpar;

    /* * UVA_10026.cpp * * Created on: 2013年10月10日 * Author: Administrator */ #include <iostream> ...

  5. uva 10026 Shoemaker&&num;39&semi;s Problem &lowbar;贪心

    题意:鞋匠现在有n个工作要做,每个工作要x天,没延迟一天需要付款y,鞋匠每天只能做一个工作,问使得鞋匠最少赔款的工作顺序. 思路:工作和工作之间排序,如果a.value*b.day>b.valu ...

  6. CF &num;296 &lpar;Div&period; 1&rpar; B&period; Clique Problem 贪心(构造)

    B. Clique Problem time limit per test 2 seconds memory limit per test 256 megabytes input standard i ...

  7. codeforces 442B B&period; Andrey and Problem&lpar;贪心&rpar;

    题目链接: B. Andrey and Problem time limit per test 2 seconds memory limit per test 256 megabytes input ...

  8. hdu----&lpar;5055&rpar;Bob and math problem&lpar;贪心&rpar;

    Bob and math problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Oth ...

  9. uva 10026 Shoemaker&&num;39&semi;s Problem

    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p ...

随机推荐

  1. JS实战 &&num;183&semi; 仿css样式选择器

    代码如下: <html> <head>     <meta http-equiv="Content-Type" content="text/ ...

  2. 简述block

    block传值也适用于从后往前传值 先介绍block的基本知识 /** * 1.如何定义一个Block变量 2.怎样给定义的Block变量赋初值 3.如何冲定义Block类型 4.如何使用Block实 ...

  3. unix编程书中的 ourhdr&period;h代码

    真心不知到里面写的具体什么意思,先记下吧. /*Our own header, to be included after all standard system headers*/ #ifndef _ ...

  4. 将16进制(HTML)颜色值转换成 Color类型

    private void btnChangeColor_Click(object sender, EventArgs e) { txtColor.BackColor = ColorTranslator ...

  5. CURD 例子

    public function modify(){ $id=$_GET['id']; $m=M('user'); $arr=$m->find($id); //var_dump($arr); $t ...

  6. SZU &colon; A18 &lpar;Climb Well&rpar;

    Judge Info Memory Limit: 32768KB Case Time Limit: 10000MS Time Limit: 10000MS Judger: Number Only Ju ...

  7. 从零开始部署小型企业级虚拟桌面 -- Vmware Horizon View 6 For Linux VDI -- 概念简介

    什么是桌面虚拟化? 桌面虚拟化有很多概念,此处谈论的,是指的一般企业使用的“服务器 + 虚拟机 + 云终端”的方式来实现的. 桌面虚拟化的原理是什么? 桌面虚拟化看上去高大上,实际上原理非常的简单.拿 ...

  8. 原生Feign使用详解

    一,简介 Feign使得 Java HTTP 客户端编写更方便.Feign 灵感来源于Retrofit.JAXRS-2.0和WebSocket.Feign最初是为了降低统一绑定Denominator到 ...

  9. (转)拉姆达表达式&lpar;Lambda Expressions&rpar; &equals;&gt&semi;写法的涵义

      lambdaclass编译器 让我们先看一个简单的拉姆达表达式: x=>x/2 这个表达式的意思是:x为参数,对x进行相应的操作后的结果作为返回值. 通过这个拉姆达表达式,我们可以看到: 这 ...

  10. ElasticSearch 2 &lpar;11&rpar; - 节点调优(ElasticSearch性能)

    ElasticSearch 2 (11) - 节点调优(ElasticSearch性能) 摘要 一个ElasticSearch集群需要多少个节点很难用一种明确的方式回答,但是,我们可以将问题细化成一下 ...