UVa Problem 10026 Shoemaker’s Problem (鞋匠的烦恼)

By | 05月24日
Advertisement

// Shoemaker’s Problem (鞋匠的烦恼) // PC/UVa IDs: 110405/10026, Popularity: C, Success rate: average Level: 2 // Verdict: Accepted // Submission Date: 2011-05-23 // UVa Run Time: 0.008s // // 版权所有(C)2011,邱秋。metaphysis # yeah dot net // // 算法:假设有 n 个订单 T1 ~ Tn,罚金分别为 S1 ~ Sn,为了让罚金尽可能少,则一个订单必须被优先处 // 理的充要条件是:设订单 Tx(Sx) 为 T1 ~ Tn中 的任意一个订单,只要满足 Tx * (未处理订单罚金总 // 和) < Sx * (未处理订单需时总和),则订单 Tx 应该被优先处理。那么比较任意两个订单 Tx 和 Ty, // 只要 Tx * Sy < Ty * Sx,则订单 Tx 应该优先处理,将订单按照以上规则排序,如果订单 Tx 与其 // 它订单都满足以上关系,则订单 Tx 必须优先被处理。 #include <iostream> #include <algorithm> using namespace std; #define MAXSIZE 1000 struct order { int days; int fine; int index; }; bool cmp(order x, order y) { return x.days * y.fine < y.days * x.fine; } int main(int ac, char *av[]) { order orders[MAXSIZE]; int capacity; int cases; cin >> cases; while (cases--) { cin >> capacity; int counter = 0; while (counter < capacity) { cin >> orders[counter].days >> orders[counter].fine; orders[counter].index = (counter + 1); counter++; } sort(orders, orders + capacity, cmp); for (int i = 0; i < capacity; i++) { cout << orders[i].index; if (i < (capacity - 1)) cout << " "; } cout << endl; if (cases) cout << endl; } return 0; }

Similar Posts:

  • uva 10026 Shoemaker&#39;s Problem

    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=967 对价钱与天数比例排序,贪心即可. 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 2000 5 using namespace std; 6

  • 10026 - Shoemaker&amp;#39;s Problem(贪心)

    该题是说有n个任务,每个任务都有一个需要的时间,还有一个价格,这个价格的意思是:在开始处理该任务之前的每一天都亏损这个价格,问最小亏损的安排是什么样的. YY了一下,发现样例是按照:价格/时间 进行了排序,其次按照编号排序. 大概的原理类似于性价比之类的吧,从样例就可以看出来,不一定要先处理价格高的就好,还有完成天数的限制. 至于这个贪心方法的证明,网上搜到一个:对于为什么贪心策略是这个样子的,我们不妨拿相邻的两个事件a.b来说明一下.由于a.b之后的事件是固定的,所以我们无论排成ab还是排成b

  • UVa 100 - The 3n + 1 problem(函数循环长度)

    题目来源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36 The 3n + 1 problem Background Problems in Computer Science are often classified as belonging to a certain class of problems

  • UVa 10245 The Closest Pair Problem (计算几何&amp;amp;最近点对)

    10245 - The Closest Pair Problem Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1186 Given a set of points in a two dimensional space, you will have to

  • Uva 17239 The 3n + 1 problem

     The 3n + 1 problem  Background Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is

  • uva 10245 - The Closest Pair Problem(暴力剪枝)

    题目连接:10245 - The Closest Pair Problem 题目大意:给出若干个点,找出两个点,使得两点间距离为所有任意两点距离中的最小值. 解题思路:本来这题应该用分治的方法去做的,但是偷了点懒,暴力剪枝过了,剪枝的方法就是将所有点按照x的大小来排序,当point[j].x - point[i].x > min(min 为当前找到的最小值),可以跳出循环,开始判断i+ 1点. #include <stdio.h> #include <string.h> #i

  • UVA - 729 The Hamming Distance Problem (全排列)

     The Hamming Distance Problem  The Hamming distance between two strings of bits (binary integers) is the number of corresponding bit positions that differ. This can be found by using XOR on corresponding bits or equivalently, by adding corresponding

  • UVa 1640 (计数) The Counting Problem

    题意: 统计[a, b]或[b, a]中0~9这些数字各出现多少次. 分析: 这道题可以和UVa 11361比较来看. 同样是利用这样一个"模板",进行区间的分块,加速运算. 因为这里没有前导0,所以分块的时候要多分几种情况. 以2345为例,这是一个四位数,首先要计算一下所有的一位数.两位数以及三位数各个数字出现的个数. 对应的模板分别为n,n*,n**,其中n代表非零数字,*代表任意数字. 考虑这样一个长为l的模板****(l个*),这样的数共10l个,而且各个数字都是等频率出现,

  • UVa 12210 - A Match Making Problem

    題目:單身那時和女士配對,每次最年長的男士和年齡最相近的女士配對, 如果男士都有伴侶則輸出0,否則輸出沒有伴侶的男士個數,并輸出年齡最小的男士年齡. 分析:簡單題.比較數量,輸出最小值即可. 如果,單身男士的數量不多餘單身女士的數量則輸出0: 否則,沒有伴侶的男士個數即為女士數量減去男士數量,并輸出年齡最小的男士年齡. 說明:這裡使用排序找最小值,枚舉更快,╮(╯▽╰)╭. #include <algorithm> #include <iostream> #include <

  • Problem B The Blocks Problem(vector的使用)

    题目链接:Problem B 题意:有n块木块,编号为0~n-1,要求模拟以下4种操作(下面的a和b都是木块编号) 1. move a onto b: 把a和b上方的木块全部归位,然后把a摞在b上面. 2. move a over b: 把a上方的木块全部归位,然后把a放在b所在木块堆的顶部. 3. pile a onto b: 把b上方的木块全部归位,然后把a及上面的木块整体摞在b上面. 4. pile a over b: 把a及上面的木块整体摞在b所在木块堆的顶部. 遇到quit时终止一组数

Tags: