题目链接: 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(贪心)的更多相关文章
-
UVA-10026 Shoemaker&#39;s Problem (贪心)
题目大意:一个鞋匠,有n只鞋要修,修某只鞋的时间ti已知,某只鞋晚修一天要交的罚款fi也已知.现在让找个修鞋顺序使得罚款最少. 题目分析:本来想水一下这道题,没想到真的AC啦.后来又查的题解,找的解释 ...
-
UVA 10026 Shoemaker&#39;s Problem 鞋匠的难题 贪心+排序
题意:鞋匠一口气接到了不少生意,但是做鞋需要时间,鞋匠只能一双一双地做,根据协议每笔生意如果拖延了要罚钱. 给出每笔生意需要的天数和每天的罚钱数,求出最小罚钱的排列顺序. 只要按罚款/天数去从大到小排 ...
-
uva 10026 Shoemaker&#39;s Problem(排序)
题目连接:10026 Shoemaker's Problem 题目大意:有一个鞋匠接了n双要修的鞋子, 修每双鞋需要d天,每推迟一天修将亏损val元,问按什么样的顺序修鞋可以保证损失最少,如果有多种情 ...
-
(贪心5.2.1)UVA 10026 Shoemaker&#39;s Problem(利用数据有序化来进行贪心选择)
/* * UVA_10026.cpp * * Created on: 2013年10月10日 * Author: Administrator */ #include <iostream> ...
-
uva 10026 Shoemaker&#39;s Problem _贪心
题意:鞋匠现在有n个工作要做,每个工作要x天,没延迟一天需要付款y,鞋匠每天只能做一个工作,问使得鞋匠最少赔款的工作顺序. 思路:工作和工作之间排序,如果a.value*b.day>b.valu ...
-
CF #296 (Div. 1) B. Clique Problem 贪心(构造)
B. Clique Problem time limit per test 2 seconds memory limit per test 256 megabytes input standard i ...
-
codeforces 442B B. Andrey and Problem(贪心)
题目链接: B. Andrey and Problem time limit per test 2 seconds memory limit per test 256 megabytes input ...
-
hdu----(5055)Bob and math problem(贪心)
Bob and math problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth ...
-
uva 10026 Shoemaker&#39;s Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p ...
随机推荐
-
JS实战 &#183; 仿css样式选择器
代码如下: <html> <head> <meta http-equiv="Content-Type" content="text/ ...
-
简述block
block传值也适用于从后往前传值 先介绍block的基本知识 /** * 1.如何定义一个Block变量 2.怎样给定义的Block变量赋初值 3.如何冲定义Block类型 4.如何使用Block实 ...
-
unix编程书中的 ourhdr.h代码
真心不知到里面写的具体什么意思,先记下吧. /*Our own header, to be included after all standard system headers*/ #ifndef _ ...
-
将16进制(HTML)颜色值转换成 Color类型
private void btnChangeColor_Click(object sender, EventArgs e) { txtColor.BackColor = ColorTranslator ...
-
CURD 例子
public function modify(){ $id=$_GET['id']; $m=M('user'); $arr=$m->find($id); //var_dump($arr); $t ...
-
SZU : A18 (Climb Well)
Judge Info Memory Limit: 32768KB Case Time Limit: 10000MS Time Limit: 10000MS Judger: Number Only Ju ...
-
从零开始部署小型企业级虚拟桌面 -- Vmware Horizon View 6 For Linux VDI -- 概念简介
什么是桌面虚拟化? 桌面虚拟化有很多概念,此处谈论的,是指的一般企业使用的“服务器 + 虚拟机 + 云终端”的方式来实现的. 桌面虚拟化的原理是什么? 桌面虚拟化看上去高大上,实际上原理非常的简单.拿 ...
-
原生Feign使用详解
一,简介 Feign使得 Java HTTP 客户端编写更方便.Feign 灵感来源于Retrofit.JAXRS-2.0和WebSocket.Feign最初是为了降低统一绑定Denominator到 ...
-
(转)拉姆达表达式(Lambda Expressions) =>;写法的涵义
lambdaclass编译器 让我们先看一个简单的拉姆达表达式: x=>x/2 这个表达式的意思是:x为参数,对x进行相应的操作后的结果作为返回值. 通过这个拉姆达表达式,我们可以看到: 这 ...
-
ElasticSearch 2 (11) - 节点调优(ElasticSearch性能)
ElasticSearch 2 (11) - 节点调优(ElasticSearch性能) 摘要 一个ElasticSearch集群需要多少个节点很难用一种明确的方式回答,但是,我们可以将问题细化成一下 ...